A major result in Descriptive Complexity reveals that NP is equal to the
set of formulas expressible in second order existential logic. Monadic NP
is a subset of second order existential logic whose second order
existential quantifiers range over unary relations. This talk will focus
on the game-theoretic technique of Ehrenfeucht and Fraisse, which is a
method of ascertaining what is and is not expressible in logics such as
Monadic NP. As an example, I will describe the result that graph
connectivity is not expressible in Monadic NP, even under "enhanced"
circumstances. The title, along with much of the content, is drawn from a
1995 paper by Fagin, Stockmeyer, and Vardi.
Last modified 5 November 2002