Lics

IEEE Symposium on Logic in Computer Science

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

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}
 }