Document Type
Report
Date
11-30-1994
Keywords
Semantics, Syntax
Language
English
Disciplines
Computer Sciences
Description/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.
Recommended Citation
Royer, James S., "Semantics vs. Syntax vs. Computations Machine Models for Type-2 Polynomial-Time Bounded Functionals (Preliminary Draft)" (1994). Electrical Engineering and Computer Science - Technical Reports. 149.
https://surface.syr.edu/eecs_techreports/149
Source
local
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-94-10
Author later published:James S Royer, Semantics vs Syntax vs Computations: Machine Models for Type-2 Polynomial-Time Bounded Functionals, Journal of Computer and System Sciences, Volume 54, Issue 3, June 1997, Pages 424-436, ISSN 0022-0000, http://dx.doi.org/10.1006/jcss.1997.1487.