## 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the IEEE Annual Structure in Complexity Theory Conference |

Editors | Anon |

Publisher | IEEE Computer Society |

Pages | 37-48 |

Number of pages | 12 |

State | Published - 1995 |

Event | Proceedings of the 10th Annual Structure in Complexity Theory Conference - Minneapolis, MN, USA Duration: Jun 19 1995 → Jun 22 1995 |

### Other

Other | Proceedings of the 10th Annual Structure in Complexity Theory Conference |
---|---|

City | Minneapolis, MN, USA |

Period | 6/19/95 → 6/22/95 |

## ASJC Scopus subject areas

- Engineering(all)