Content deleted Content added
Correct description of SO quantification in MSO. |
→top: rewrite example for clarity |
||
Line 3:
Second-order logic allows quantification over [[Predicate (mathematical logic)|predicates]]. However, MSO is the [[Fragment (logic)|fragment]] in which second-order quantification is limited to monadic predicates (predicates having a single argument). This is often described as quantification over "sets" because monadic predicates are equivalent in expressive power to sets (the set of elements for which the predicate is true).
Existential monadic second-order logic (EMSO) is the fragment of MSO in which all quantifiers over sets must be [[existential quantifier]]s, outside of any other part of the formula. The first-order quantifiers are not restricted. By analogy to [[Fagin's theorem]], according to which existential (non-monadic) second-order logic captures precisely the [[descriptive complexity]] of the complexity class [[NP (complexity)|NP]], the class of problems that may be expressed in existential monadic second-order logic has been called monadic NP. The restriction to monadic logic makes it possible to prove separations in this logic that remain unproven for non-monadic second-order logic
| last = Fagin | first = Ronald | author1-link = Ronald Fagin
| journal = Zeitschrift für Mathematische Logik und Grundlagen der Mathematik
Line 18:
| publisher = Institute of Electrical and Electronics Engineers
| title = Proceedings of the Eighth Annual Structure in Complexity Theory Conference
| year = 1993}}.</ref> The existence of an analogous pair of complementary problems, only one of which has an existential second-order formula (without the restriction to monadic formulas) is equivalent to the equality of NP and [[coNP]], an open question in computational complexity.
==References==
| |||