On monadic NP vs. monadic co-NP
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
It is proved that connectivity of finite graphs is not in monadic NP, even in the presence of arbitrary built-in relations of moderate degree (that is, degree (log n) /sup o(1)/). This results in a strong separation between monadic NP and monadic co-NP. The proof uses a combination of three techniques: (1) a technique of W. Hanf (1965) for showing that two (infinite) structures agree on all first-order sentences, under certain conditions; (2) a recent approach to second-order Ehrenfeucht-Fraisse games by M. Ajtai and R. Fagin (1990); and (3) playing Ehrenfeucht-Fraisse games over random structures. Regarding (1), a version of Hanf's result that is better suited for use as a tool in inexpressibility proofs for classes of finite structures is given. The power of these techniques is further demonstrated by using the first two techniques to give a very simple proof of the separation of monadic NP from monadic co-NP without the presence of built-in relations.<>Keywords
This publication has 20 references indexed in Scilit:
- On monadic NP vs. monadic co-NPPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On logics, tilings, and automataPublished by Springer Nature ,1991
- Theory of database queriesPublished by Association for Computing Machinery (ACM) ,1988
- Second-order and Inductive Definability on Finite StructuresMathematical Logic Quarterly, 1987
- Relational queries computable in polynomial timeInformation and Control, 1986
- On the definability of properties of finite graphsDiscrete Mathematics, 1984
- Structure and complexity of relational queriesJournal of Computer and System Sciences, 1982
- On logics of discoveryLecture Notes in Computer Science, 1975
- Monadic generalized spectraMathematical Logic Quarterly, 1975
- A spectrum hierarchyMathematical Logic Quarterly, 1975