Invited Paper: The Quest for a Logic Capturing PTIME (at LICS 2008)

Authors: Martin Grohe

Abstract

The question of whether there is a logic that captures polynomial time is thecentral open problem in descriptive complexity theory. In my talk, I will review the question and the early, mostly negative results that were obtained until the mid 1990s, and then move on to positive results about capturing polynomial time on specific classes of graphs. This will include recent results on definability in fixed-point logic and graph structure theory. Finally, I will dicuss stronger logics and propose directions for further research.The purpose of this accompanying note is to give the basic definitions in detail, state the main results, mention some open problems, and give a list of references.

BibTeX

  @InProceedings{Grohe-TheQuestforaLogicCa,
    author = 	 {Martin Grohe},
    title = 	 {The Quest for a Logic Capturing PTIME},
    booktitle =  {Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008)},
    year =	 {2008},
    month =	 {June}, 
    pages =      {267--271},
    location =   {Pittsburgh, PA, USA}, 
    note =       {Invited Talk},
    publisher =	 {IEEE Computer Society Press}
  }