10
$\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?

$\endgroup$
  • 2
    $\begingroup$ The elements of P and NP are sets of models. $\endgroup$ – András Salamon Aug 9 '10 at 18:42
10
$\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)$.

$\endgroup$
  • $\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 '10 at 1:29
  • $\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 '10 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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