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 examplesEdit

We define second-order variable, a SO variable has got an arity   and represent any proposition of arity  , i.e. a subset of the  -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.

PropertyEdit

Normal formEdit

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 classesEdit

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   which is NP, and with only universal quantification is equal to   which is Co-NP.

Adding restrictionsEdit

Horn formulae are equal to PEdit

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 formulae 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 NLEdit

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 formulae can be made in prenex form where the second order is existential and the first order universal without loss of generalities.

Transitive closure is PSPACEEdit

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 EXPTIMEEdit

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.

IteratingEdit

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:

  •   is equal to PSPACE it is also another way to write SO(TC).
  •   is equal to EXPTIME it is also another way to write SO(LFP)

See alsoEdit

ReferencesEdit

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

External linksEdit