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

Authors:**Goerdt, A.**

### 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 = {Goerdt, A.}, title = {Characterizing complexity classes by higher type primitive recursive definitions }, booktitle = {Proceedings of the Fourth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1989}, year = 1989, editor = {Rohit Parikh}, month = {June}, pages = {364--374}, location = {Pacific Grove, CA, USA}, publisher = {IEEE Computer Society Press} }