On Limitations of the Ehrenfeucht-Fraïssé-method in Descriptive Complexity

Yijia Chen (Invited Speaker)

9:30 - 10:30AM, Sun, Jun 25.

Ehrenfeucht-Fraïssé games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as P = NP or NP = 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-Fraïssé game. We obtain similar results for the so-called Ajtai-Fagin games and for a variant where the structures are obtained randomly.

[Back to Schedule]