Closure of monadic NP

Abstract

Monadic NP is the class of problems expressible in monadic ∑11, i.e., ∑11 with the restriction that the second-order quantifiers are all unary, and hence range only over sets. Closed monadic NP is the closure of monadic NP under first-order quantification and existential unary second-order quantifiers. Thus, closed monadic NP differs from monadic NP in that the possibility of arbitrary interleavings of first-order quantifiers is allowed among the existential unary second-order quantifiers. Closed monadic NP is a natural, rich and robust subclass of NP. Closed monadic NP contains an undirected graph property not in the closure of monadic NP under first-order quantification and Boolean operation.