Graph Connectivity and Monadic NP

Ehrenfeucht games are a useful tool in proving that certain properties of finite structures are not expressible by formulas of a certain type. In this paper a new method is introduced that allows the extension of a local winning strategy for Duplicator, one of the two players in Ehrenfeucht games, to a global winning strategy. As an application it is shown that graph connectivity cannot be expressed by existential second-order formulas, where the second-order quantification is restricted to unary relations (monadic NP), even, in the presence of a built-in linear order. As a second application it is stated, that, on the other hand, the presence of a linear order increases the power of monadic NP more than the presence of a successor relation. >

Authors

• Thomas Schwentick

Keywords

• Complexity theory
• Game theory
• Weak Connections
• Linear Order
• Finite Structure
• Isomorphism
• Set Of Structures
• Idea Of The Proof
• Permutation Group