Seminar


Type-two poly-time and length revisions

The talk presents an alternate characterization of type-two polynomial-time computability, with the goal of making second-order complexity theory more approachable. The characterization relies on the usual oracle machines to model programs with subroutine calls, but the use of higher-order objects as running times is avoided. This is achieved by refining the notion of oracle-polynomial-time introduced by Cook by imposing a further restriction on the oracle interactions. Both the restriction as well as its purpose are very simple: it is well-known that Cook's model allows polynomial depth iteration of functional inputs with no restrictions on size, and thus does not guarantee that operators from the class preserve polynomial-time computability. We restrict the number of lookahead revisions, that is the number of times a query can be asked that is bigger than any of the previous queries and prove that this leads to a class of feasible functionals. Furthermore, all feasible problems can be solved within this class if one is allowed to separate a task into efficiently solvable subtasks. More formally put: the closure of the class under lambda-abstraction and application includes all feasible operations. This has consequences for a very similar class of strongly polynomial-time computable operators previously considered by Kawamura and Steinberg: It turns out to have the same closure property. This can be attributed to properties of the limited recursion operator, which is not strongly polynomial-time computable but decomposes into two such operations and lies in the broader class.