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?



Your Answer

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