Tags:descriptive complexity, monadic NP and ximplified proofs
Abstract:
I will discuss ways to simplify inexpressibility proofs. In particular, I will discuss an approach by Fagin, Stockmeyer and Vardi that greatly simplifies my earlier proof (from my Ph.D. thesis) that monadic NP is not closed under complement, where monadic NP consists of properties defined by existential second-order sentences, where the existential second-order quantifiers range only over subsets of the domain.