11
$\begingroup$

Prompted by Vinay Deolalikar's purported proof of P != NP, I've been reading up on Descriptive Complexity for some background material.

The major successes of Descriptive Complexity include Fagin's result that $NP=SO\exists$ (that is, the class NP is equal to the class of models of a second-order existential query over some vocabulary), and also that $P = FO(LFP)$ (that the class P is equal to the class of models of first-order queries that might use a Least-Fixed-Point operator), and also $PH = SO$.

My understanding of mathematical logic is quite shaky, but from what I understand, second-order formulas are not expressible in first order logic - how does this fact stand in relation to the results I mentioned above? Why does it not separate NP from P, or PH from P?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ The elements of P and NP are sets of models. $\endgroup$
    – András Salamon
    Aug 9, 2010 at 18:42

1 Answer 1

Reset to default
11
$\begingroup$

Remember that this is finite model theory and it is quite different from logic on infinite structures, e.g. satisfiability of first-order formulas on finite structures is $\Sigma_1$, whereas the same question is $\Pi_1$ for general structures (where the formula is satisfiable iff it does not lead to (i.e. prove) contradiction).

It is not known yet if the properties of the finite structures expressible in SO are different from those expressible in $FO(LFP)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the answer - that clarifies much. But, what did you mean by "whereas the same question is in Pi_1" - what same question? $\endgroup$
    – Henry Yuen
    Aug 10, 2010 at 1:29
  • 1
    $\begingroup$ Thank you. I was referring to satisfiability of a formula over general (i.e. not necessary finite) structures. If we are given a first-order formula, it has a model iff it is consistent (by completeness theorem for first-order logic), and this is $\Pi_1$ property: $\varphi$ is satisfiable iff $\forall \pi, \pi is not a proof of \varphi \vdash \bot$. $\endgroup$
    – Kaveh
    Aug 10, 2010 at 2:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.