On some natural complete operators

An operator is a mapping from integer functions to integer functions. It is known, from a result by Baker, Gill and Solovay (1975), that there exists an operator computable in polynomial time by a nondeterministic oracle Turing machine (called an NP operator) but not computable in polynomial time by any deterministic oracle Turing machine. We investigate several natural operators which share similar properties. We use the concept of completeness to give a precise classification of the complexity of these operators. For example, the question of finding maximum values of polynomial-time computable functions can be formulated as an operator complete for the class of NP operators.

Authors

• Ker-I Ko

Keywords

No keywords are indexed for this paper.