Fagin's Theorem (see Wikipedia and these lecture notes) states that there is an equivalence between second-order logic (SOL) formulas with existential quantifiers, and problems in NP.

I was wondering if we can also extend this result to other complexity classes in the polynomial hierarchy?

For example, can we state that deciding any SOL formula of the following form $\exists \forall \phi $ is in the ${‎‎\sum^{P}_2}$ (a.k.a., S2P) complexity class? Recall that S2P is the complexity class of all problems which we can solve in NP, given that we can solve co-NP problems in constant time (e.g., $\exists x_1, \ldots, x_n\forall y_1, \ldots, y_m \space \psi$, for a 3-SAT formula $\psi$).

It inductively seems to be possible to extend Fagin's theorem for these cases but would appreciate any feedback.

Thanks very much!

  • 1
    $\begingroup$ $S_2^P$ is a different (smaller) class than $\Sigma_2^P$. But otherwise, yes: $\Sigma_k^P$ coincides with languages with languages definable by $\exists_k$ SO sentences (i.e., with $k$ alternating blocks of SO quantifiers, starting with an existential block, followed by an FO formula). $\endgroup$ Commented Feb 16 at 14:04
  • $\begingroup$ Thanks very much Emil! Also, is it possible to briefly emphasize the difference between Sigma_{2}^{P} and S2P? In what sense is S2pP ``smaller''? Thanks very much again! $\endgroup$
    – UserA2000
    Commented Feb 17 at 9:27
  • $\begingroup$ See en.m.wikipedia.org/wiki/… $\endgroup$ Commented Feb 17 at 9:45


Your Answer

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