Polynomial running times for polynomial-time oracle machines

Akitoshi Kawamura, Florian Steinberg

This paper introduces a more restrictive notion of feasibility of functionals on Baire space than the established one from second-order complexity theory. Thereby making it possibl…