Bruce Kapron

University of Victoria

FEASIBLY CONTINUOUS TYPE-2 FUNCTIONALS

DIMACS Center - Room 433 (small conference room)

Busch Campus

Piscataway, New Jersey

July 22, 2:30 p.m.

Abstract:

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