Characterizing complexity classes by higher type: Primitive recursive definitions, Part II

Andreas Goerdt; Helmut Seidl

doi:10.1007/3-540-53414-8_37

Characterizing complexity classes by higher type: Primitive recursive definitions, Part II

Andreas Goerdt, Helmut Seidl

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

Abstract

Higher type primitive recursive definitions (also known as Gödel's system T) defining first-order functions (i.e. functions of type ind→…→ind→ind, ind for individuals, higher types occur in between) can be classified into an infinite syntactic hierarchy: A definition is in the n'th stage of this hierarchy, a so called rank-n-definition, iff n is an upper bound on the levels of the types occurring in it. We interpret these definitions over finite structures and show for n≥1: Rank-(2n+2)-definitions characterize (in the sense of, say) the complexity class DTIME(exp_n(poly)) whereas rank-(2n+3)-definitions characterize DSPACE(exp_n(poly)) (here exp₀(x) = x, exp_n+1(x)=2^expnx). This extends the results that rank-1-definitions characterize LOGSPACE, rank-2-definitions characterize PTIME, rank-3-definitions characterize PSPACE, rank-4-definitions characterize EXPTIME[Go89a].

Original language	English
Title of host publication	Aspects and Prospects of Theoretical Computer Science - 6th International Meeting of Young Computer Scientists, Proceedings
Editors	Jurgen Dassow, Jozef Kelemen
Publisher	Springer Verlag
Pages	148-158
Number of pages	11
ISBN (Print)	9783540534143
DOIs	https://doi.org/10.1007/3-540-53414-8_37
State	Published - 1990
Externally published	Yes
Event	6th International Meeting of Young Computer Scientists, IMYCS 1990 - Smolenice, Slovakia Duration: 19 Nov 1990 → 23 Nov 1990

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	464 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th International Meeting of Young Computer Scientists, IMYCS 1990
Country/Territory	Slovakia
City	Smolenice
Period	19/11/90 → 23/11/90

Access to Document

10.1007/3-540-53414-8_37

Cite this

Goerdt, A., & Seidl, H. (1990). Characterizing complexity classes by higher type: Primitive recursive definitions, Part II. In J. Dassow, & J. Kelemen (Eds.), Aspects and Prospects of Theoretical Computer Science - 6th International Meeting of Young Computer Scientists, Proceedings (pp. 148-158). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 464 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-53414-8_37

Goerdt, Andreas ; Seidl, Helmut. / Characterizing complexity classes by higher type : Primitive recursive definitions, Part II. Aspects and Prospects of Theoretical Computer Science - 6th International Meeting of Young Computer Scientists, Proceedings. editor / Jurgen Dassow ; Jozef Kelemen. Springer Verlag, 1990. pp. 148-158 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{493cc518faf5426f820952d51411dd25,

title = "Characterizing complexity classes by higher type: Primitive recursive definitions, Part II",

abstract = "Higher type primitive recursive definitions (also known as G{\"o}del's system T) defining first-order functions (i.e. functions of type ind→…→ind→ind, ind for individuals, higher types occur in between) can be classified into an infinite syntactic hierarchy: A definition is in the n'th stage of this hierarchy, a so called rank-n-definition, iff n is an upper bound on the levels of the types occurring in it. We interpret these definitions over finite structures and show for n≥1: Rank-(2n+2)-definitions characterize (in the sense of, say) the complexity class DTIME(expn(poly)) whereas rank-(2n+3)-definitions characterize DSPACE(expn(poly)) (here exp0(x) = x, expn+1(x)=2expnx). This extends the results that rank-1-definitions characterize LOGSPACE, rank-2-definitions characterize PTIME, rank-3-definitions characterize PSPACE, rank-4-definitions characterize EXPTIME[Go89a].",

author = "Andreas Goerdt and Helmut Seidl",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1990.; 6th International Meeting of Young Computer Scientists, IMYCS 1990 ; Conference date: 19-11-1990 Through 23-11-1990",

year = "1990",

doi = "10.1007/3-540-53414-8_37",

language = "English",

isbn = "9783540534143",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "148--158",

editor = "Jurgen Dassow and Jozef Kelemen",

booktitle = "Aspects and Prospects of Theoretical Computer Science - 6th International Meeting of Young Computer Scientists, Proceedings",

}

Goerdt, A & Seidl, H 1990, Characterizing complexity classes by higher type: Primitive recursive definitions, Part II. in J Dassow & J Kelemen (eds), Aspects and Prospects of Theoretical Computer Science - 6th International Meeting of Young Computer Scientists, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 464 LNCS, Springer Verlag, pp. 148-158, 6th International Meeting of Young Computer Scientists, IMYCS 1990, Smolenice, Slovakia, 19/11/90. https://doi.org/10.1007/3-540-53414-8_37

Characterizing complexity classes by higher type: Primitive recursive definitions, Part II. / Goerdt, Andreas; Seidl, Helmut.
Aspects and Prospects of Theoretical Computer Science - 6th International Meeting of Young Computer Scientists, Proceedings. ed. / Jurgen Dassow; Jozef Kelemen. Springer Verlag, 1990. p. 148-158 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 464 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Characterizing complexity classes by higher type

T2 - 6th International Meeting of Young Computer Scientists, IMYCS 1990

AU - Goerdt, Andreas

AU - Seidl, Helmut

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1990.

PY - 1990

Y1 - 1990

N2 - Higher type primitive recursive definitions (also known as Gödel's system T) defining first-order functions (i.e. functions of type ind→…→ind→ind, ind for individuals, higher types occur in between) can be classified into an infinite syntactic hierarchy: A definition is in the n'th stage of this hierarchy, a so called rank-n-definition, iff n is an upper bound on the levels of the types occurring in it. We interpret these definitions over finite structures and show for n≥1: Rank-(2n+2)-definitions characterize (in the sense of, say) the complexity class DTIME(expn(poly)) whereas rank-(2n+3)-definitions characterize DSPACE(expn(poly)) (here exp0(x) = x, expn+1(x)=2expnx). This extends the results that rank-1-definitions characterize LOGSPACE, rank-2-definitions characterize PTIME, rank-3-definitions characterize PSPACE, rank-4-definitions characterize EXPTIME[Go89a].

AB - Higher type primitive recursive definitions (also known as Gödel's system T) defining first-order functions (i.e. functions of type ind→…→ind→ind, ind for individuals, higher types occur in between) can be classified into an infinite syntactic hierarchy: A definition is in the n'th stage of this hierarchy, a so called rank-n-definition, iff n is an upper bound on the levels of the types occurring in it. We interpret these definitions over finite structures and show for n≥1: Rank-(2n+2)-definitions characterize (in the sense of, say) the complexity class DTIME(expn(poly)) whereas rank-(2n+3)-definitions characterize DSPACE(expn(poly)) (here exp0(x) = x, expn+1(x)=2expnx). This extends the results that rank-1-definitions characterize LOGSPACE, rank-2-definitions characterize PTIME, rank-3-definitions characterize PSPACE, rank-4-definitions characterize EXPTIME[Go89a].

UR - http://www.scopus.com/inward/record.url?scp=33746047523&partnerID=8YFLogxK

U2 - 10.1007/3-540-53414-8_37

DO - 10.1007/3-540-53414-8_37

M3 - Conference contribution

AN - SCOPUS:33746047523

SN - 9783540534143

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 148

EP - 158

BT - Aspects and Prospects of Theoretical Computer Science - 6th International Meeting of Young Computer Scientists, Proceedings

A2 - Dassow, Jurgen

A2 - Kelemen, Jozef

PB - Springer Verlag

Y2 - 19 November 1990 through 23 November 1990

ER -

Goerdt A, Seidl H. Characterizing complexity classes by higher type: Primitive recursive definitions, Part II. In Dassow J, Kelemen J, editors, Aspects and Prospects of Theoretical Computer Science - 6th International Meeting of Young Computer Scientists, Proceedings. Springer Verlag. 1990. p. 148-158. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-53414-8_37

Characterizing complexity classes by higher type: Primitive recursive definitions, Part II

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this