Dr. Bruce Kapron, University of Victoria, Department of Computer Science
Old and new results for type-two feasibility
Abstract: Computational complexity theory traditionally considers computation over discrete finite inputs, and in this setting there is a standard notion of feasibility, namely poly-time computability. Is it possible to extend this notion to settings where inputs are infinite or even continuous? In this talk I will consider one simple extension, where inputs are functions mapping strings to strings. After reviewing some motivating examples, as well as basic ideas and classic results in this model, I will discuss some challenges to formulating an intuitive and natural model for type-two feasibility. Finally, I will present some recent work on developing a more natural model.