Semantics versus syntax versus computations machine models for type-2 polynomial-time bounded functionals

James S Royer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

This paper investigates analogs of the Kreisel-Lacombe-Shoenfield Theorem in the context of the type-2 basic feasible functionals, a.k.a. the Mehlhorn-Cook class of type-2 polynomial-time functionals. We develop a direct, polynomial-time analog of effective operation, where the time bound on computations is modeled after Kapron and Cook's scheme for their basic polynomial-time functionals. We show that (i) if P = NP, these polynomial-time effective operations are strictly more powerful on R (the class of recursive functions) than the basic feasible functions, and (ii) there is an oracle relative to which these polynomial-time effective operations and the basic feasible functionals have the same power on R. We also consider a weaker notion of polynomial-time effective operation where the machines computing these functionals have access to the computations of their 'functional' parameter, but not to its program text. For this version of polynomial-time effective operation, the analog of the Kreisel-Lacombe-Shoenfield is shown to hold - their power matches that of the basic feasible functionals on R.

Original languageEnglish (US)
Title of host publicationProceedings of the IEEE Annual Structure in Complexity Theory Conference
Editors Anon
PublisherIEEE Computer Society
Pages37-48
Number of pages12
StatePublished - 1995
EventProceedings of the 10th Annual Structure in Complexity Theory Conference - Minneapolis, MN, USA
Duration: Jun 19 1995Jun 22 1995

Other

OtherProceedings of the 10th Annual Structure in Complexity Theory Conference
CityMinneapolis, MN, USA
Period6/19/956/22/95

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Semantics versus syntax versus computations machine models for type-2 polynomial-time bounded functionals'. Together they form a unique fingerprint.

  • Cite this

    Royer, J. S. (1995). Semantics versus syntax versus computations machine models for type-2 polynomial-time bounded functionals. In Anon (Ed.), Proceedings of the IEEE Annual Structure in Complexity Theory Conference (pp. 37-48). IEEE Computer Society.