Paper: Characterizing complexity classes by higher type primitive recursive definitions (at LICS 1989)

Authors: Andreas Goerdt

Abstract

Higher type primitive recursive definitions (also known as Godel's system T) defining first-order functions can be classified into an infinite syntactic hierarchy. A definition is in the nth level of this hierarchy, a so-called rank-n definition, if and only if n is an upper bound on the levels of the types occurring in it. The author interprets these definitions over finite structures and shows that rank-2 definitions characterize PTIME, rank-3 definitions characterize PSPACE, and rank-4 definitions EXPTIME

BibTeX

  @InProceedings{Goerdt-Characterizingcompl,
    author = 	 {Andreas Goerdt},
    title = 	 {Characterizing complexity classes by higher type primitive recursive definitions },
    booktitle =  {Proceedings of the Fourth Annual IEEE Symposium on Logic in Computer Science (LICS 1989)},
    year =	 {1989},
    month =	 {June}, 
    pages =      {364--374},
    location =   {Pacific Grove, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }