Content deleted Content added
link Fragment (logic) |
orig link |
||
Line 2:
Existential monadic second-order logic (EMSO) is the [[Fragment (logic)|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; for instance, testing the [[Connectivity (graph theory)|connectivity of graphs]] belongs to monadic co-NP (the [[Complement (set theory)|complement]] of monadic NP) but not to monadic NP itself.<ref>{{citation
| last = Fagin | first = Ronald | author1-link = Ronald Fagin
| journal = Zeitschrift für Mathematische Logik und Grundlagen der Mathematik
| mr = 0371623
| pages = 89–96
| title = Monadic generalized spectra
| volume = 21
| year = 1975}}.</ref><ref>{{citation
| last1 = Fagin | first1 = R. | author1-link = Ronald Fagin
| last2 = Stockmeyer | first2 = L. | author2-link = Larry Stockmeyer
| |||