Feasibly continuous type-two functionals

Research paper by B.M. Kapron

Indexed on: 01 Nov '99Published on: 01 Nov '99Published in: Computational Complexity


A well-known theorem of type-two recursion theory states that a functional is continuous if and only if it is computable relative to some oracle. We show that a feasible analogue of this theorem holds, using techniques originally developed in the study of Boolean decision tree complexity.