Feasibly continuous type-two functionals

Authors
Citation
Bm. Kapron, Feasibly continuous type-two functionals, COMP COMPLE, 8(2), 1999, pp. 188-201
Citations number
14
Categorie Soggetti
Engineering Mathematics
Journal title
COMPUTATIONAL COMPLEXITY
ISSN journal
10163328 → ACNP
Volume
8
Issue
2
Year of publication
1999
Pages
188 - 201
Database
ISI
SICI code
1016-3328(1999)8:2<188:FCTF>2.0.ZU;2-N
Abstract
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 s how that a feasible analogue of this theorem holds, using techniques origin ally developed in the study of Boolean decision tree complexity.