On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity

Jörg Flum

Ehrenfeucht-Fraisse games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems as P \not= NP or NP \not= coNP no progress has been achieved using the games. We show that for these problems it is already hard to get the board for the corresponding Ehrenfeucht-Fraisse game.