The closure of monadic NP

It is a well-known result of Fagin that the complexity class NP coincides w ith the class of problems expressible in existential second-order logic (Si gma(1)(1)), which allows sentences consisting of a string of existential se cond-order quantifiers followed by a first-order formula. Monadic NP is the class of problems expressible in monadic Sigma(1)(1), i.e., Sigma(1)(1) wi th the restriction that the second-order quantifiers are all unary and henc e range only over sets (as opposed to ranging over, say, binary relations). For example, the property of a graph being 3-colorable belongs to monadic NP, because 3-colorability can be expressed by saying that there exists thr ee sets of vertices such that each vertex is in exactly one of the sets and no two vertices in the same set are connected by an edge. Unfortunately, m onadic NP is not a robust class, in that it is not closed under first-order quantification. We define closed monadic Nr to be the closure of monadic N P under first-order quantification and existential unary second-order quant ification. Thus, closed monadic NP differs fi om monadic NP in that we allo w the possibility of arbitrary interleavings of first-order quantifiers amo ng the existential unary second-order quantifiers. We show that closed mona dic NP is a natural, rich, and robust subclass of NP. As evidence for its r ichness, we show that not only is it a proper extension of monadic NP, but that it contains properties not ill various other extensions of monadic NP. In particular. we show that closed monadic NP contains an undirected graph property not in the closure of monadic NP under first-order quantification and Boolean operations. Our lower-bound proofs require a number of neu gam e-theoretic techniques. (C) 2000 Academic Press.