Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-065 | 21st April 2013 09:46

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

RSS-Feed




TR13-065
Authors: Yijia Chen, Joerg Flum
Publication: 22nd April 2013 21:38
Downloads: 1477
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint