Fifteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2000)

Invited Talk: Logic, Complexity, and Games (at LICS 2000)

Authors: Ronald Fagin


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.


    author = 	 {Ronald Fagin},
    title = 	 {Logic, Complexity, and Games},
    booktitle =  {Proceedings of the Fifteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2000},
    year =	 2000,
    editor =	 {Martin Abadi},
    month =	 {June}, 
    pages =      {3},
    location =   {Santa Barbara, CA, USA}, 
    note =       {Invited Talk},
    publisher =	 {IEEE Computer Society Press}