Semantics vs Syntax vs Computations: Machine Models for Type-2 Polynomial-Time Bounded Functionals

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