Paper Info
Title
Logic, Complexity, and Games
Abstract
In this talk, I will discuss an approach to the P = NP question via the correspondence between logic and complexity. The focus will be on the possible use of Ehrenfeucht-Fraíssé games.
Year
DOI
Venue
2000
10.1109/LICS.2000.855750
LICS
Keywords
Field
DocType
possible use,np question,game theory,polynomials,computational complexity,logic
PH,Quantum complexity theory,Computational logic,Discrete mathematics,Average-case complexity,Structural complexity theory,Computer science,Theoretical computer science,Descriptive complexity theory,UP,Game complexity
Conference
ISSN
ISBN
Citations 
1043-6871
0-7695-0725-5
0
PageRank 
References 
Authors
0.34
1
1
Name
Order
Citations
PageRank
Ronald Fagin188082643.66