Revision as of 17:28, 3 November 2017 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,802 edits →top: rewrite example for clarity ← Previous edit		Revision as of 17:29, 3 November 2017 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,802 edits →top: inequality not equaLITY Next edit →
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~~inequality of NP and [[coNP]], an open question in computational complexity. ==References==

Monadic second-order logic: Difference between revisions