SO (complexity)

Second-order logic is an extension of first-order with second order quantifiers, hence the reader should first read FO (complexity) to be able to understand this article. In descriptive complexity we can see that the languages recognised by SO formulae are exactly equal to the languages decided by Turing machines in the polynomial hierarchy. Extensions of SO with some operators also give us the same expressivity given by some well known complexity class,^[1] so it is a way to do proofs about the complexity of some problems without having to go to the algorithmic level.

Definition and examples

We define second-order variable, a SO variable has got an arity $k$ and represent any proposition of arity $k$ , i.e. a subset of the $k$ -tuples of the universe. They are usually written in upper-case. Second order logic is the set of FO formulae where we add quantification over second-order variables, hence we will use the terms defined in the FO article without defining them again.

Property

Normal form

Every formula is equivalent to a formula in prenex normal form, where we first write quantification on variable on second order and then a FO-formula in prenex normal form.

Relation to complexity classes

SO is equal to Polynomial hierarchy, more precisely we have that formula in prenex normal form where existential and universal of second order alternate k times are the kth level of the polynomial hierarchy.

This means that SO with only existential second-order quantification is equal to $\Sigma ^{1}$ which is NP, and with only universal quantification is equal to $\Pi ^{1}$ which is Co-NP.

Adding restrictions

Horn formulae are equal to P

SO(horn) is the set of boolean queries definable with SO formulae in disjunctive normal form such that the first order quantifiers are all universal and the quantifier-free part of the formula is in Horn form, which means that it is a big AND of OR, and in each "OR" every variable except possibly one are negated.

This class is equal to P.

Those formulaes can be made in prenex form where the second order is existential and the first order universal without loss of generalities.

Krom formulae are equal to NL

SO(Krom) is the set of boolean queries definable with second-order formulae in conjunctive normal form such that the first order quantifiers are universal and the quantifier-free part of the formula is in Krom form, which means that the first order formula is a big AND of OR, and in each "OR" there is at most two variables.

This class is equal to NL.

Those formulaes can be made in prenex form where the second order is existential and the first order universal without loss of generalities.

Transitive closure is PSPACE

SO(TC) is to SO what FO(TC) is to FO. The TC operator can now also take second-order variable as argument. SO(TC) is equal to PSPACE.

Least fixed point is EXPTIME

SO(LFP) is to SO what FO(LFP) is to FO. The LFP operator can now also take second-order variable as argument. SO(LFP) is equal to EXPTIME.

Iterating

SO(t(n)) is to SO what FO[t(n)] is to FO. But we now also have second-order quantifier in the quantifier block. It is known that:

${\mathsf {SO}}[n^{O(1)}]$ is equal to PSPACE it is also another way to write SO(TC).
${\mathsf {SO}}[2^{n^{O(1)}}]$ is equal to EXPTIME it is also another way to write SO(LFP)

References

^ *N. Immerman Descriptive complexity (1999 Springer), All information in this article can be checked in this book.

External links

Complexity zoo about SO, see the class under it also.

[1] *N. Immerman Descriptive complexity (1999 Springer), All information in this article can be checked in this book.

[1]