MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
The elements of P and NP are sets of models. – András Salamon Aug 9 '10 at 18:42
up vote 9 down vote accepted

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)$.

share|cite|improve this answer
Thanks for the answer - that clarifies much. But, what did you mean by "whereas the same question is in Pi_1" - what same question? – Henry Yuen Aug 10 '10 at 1:29
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$. – Kaveh Aug 10 '10 at 2:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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