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

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