3
$\begingroup$

While i am reading Descriptive complexity of #P functions (Saluja) in theorem 1 he state that #FO coincides #P on ordered structures.

This is a corollary from fagin’s theorem. I have read fagin’s theorem in Libkin - Elements of finite Model theory. If we have a Polynomial NTM, there is a ESO sentence that describe the existence of an accepting computation path on encoding of a finite structure. Suppose $\exists \vec{X} \phi_{M}(\vec{X})$ is such a sentence for a polynomial NTM $M$. Why we can not conclude: $$ |\{ \vec{R} : \mathfrak{A} \vDash \phi_{M}(\vec{R}/\vec{X}) \} | = | \text{accepting path of }M(enc(\mathfrak{A})) | $$

This is only possible if there is a case such that we count a same computation twice. Why with no built-in order in structure this could be happend? How is it possible to choose two distict assignment to second order variables $\vec{X}$ such that the resulting second order sentence describe the same computation path?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.