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

摘要

The paper investigates analogs of the Kreisel-Lacombe-Shoenfield (1957) Theorem in the context of the type-2 basic feasible functionals, aka 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 (1990) scheme for their basic polynomial-time functionals. We show that (i) if P=NP, these polynomial-time effective operations are strictly more powerful on /spl Rscr/ (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 /spl Rscr/. 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 /spl Rscr/.