On monadic NP vs. monadic co-NP

Abstract

It is a well-known result of Fagin that NP coincides with the class of problems expressible in existential second-order logic (Σ11). Monadic NP is the class of problems expressible in monadic Σ11, i.e., Σ11 with restriction that the second-order quantifiers range only over sets (as opposed to ranging over, say, binary relations). We prove 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)o(1)). This results in a strong separation between monadic NP and monadic co-NP, extending earlier results of Fagin and de Rougemont. Our proof uses a combination of three techniques: (1) an old technique of Hanf for showing that two (infinite) structures agree on all first-order sentences, under certain conditions, (2) a recent new approach to second-order Ehrenfeucht-Fraisse games by Ajtai and Fagin, and (3) playing Ehrenfeucht-Fraisse games over random structures (this was also used by Ajtai and Fagin). Regarding (1), we give a version of Hanf's result that is better suited for use as a tool in inexpressibility proofs for classes of finite structures. The power of these techniques is further demonstrated by using them (actually, using just 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.