SO (complexity)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Second-order logic is an extension of first-order with second orders 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 is exactly equal to the language decided by a Turing machine in the polynomial hierarchy. Extensions of SO with some operators also give us the same expressivity than 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[edit]

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[edit]

Normal form[edit]

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[edit]

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[edit]

Horn formulae are equal to P[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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:

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

See also[edit]

References[edit]

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

External links[edit]