Js. Royer, SEMANTICS VS SYNTAX VS COMPUTATIONS - MACHINE MODELS FOR TYPE-2 POLYNOMIAL-TIME BOUNDED FUNCTIONALS, Journal of computer and system sciences, 54(3), 1997, pp. 424-436
Citations number
26
Categorie Soggetti
System Science","Computer Science Hardware & Architecture","Computer Science Theory & Methods
This paper investigates analogs of the Kreisel-Lacombe-Shoenfield Theo
rem in the context of the type-2 basic feasible functionals. We develo
p a direct, polynomial-time analog of effective operation in which the
time bounding on computations is modeled after Kapron and Cook's sche
me for their basic polynomial-time functionals. We show that if P = NP
, these polynomial-time effective operations are strictly more powerfu
l on R (the class of recursive functions) than the basic feasible func
tions. We also consider a weaker notion of polynomial-time effective o
peration where the machines computing these functionals have access to
the computations of their procedural parameter, but not to its progra
m 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. (C) 1997 Academic
Press.