On some natural complete operators (Q1064780)

Call a mapping from integer functions to integer functions an operator. Complexity classes of operators can be defined via oracle Turing machines. For instance, we can define \(P_{op}\) \((NP_{op})\) to be the class of operators computable in polynomial time by deterministic (nondeterministic, respectively) oracle Turing machines. \textit{T. Baker, J. Gill} and \textit{R. Solovay} [SIAM J. Comput. 4, 431-442 (1975; Zbl 0323.68033)] showed that \(P_{op}\neq NP_{op}\). This paper defines the concept of (polynomial-time) reducibilities on operators and the concept of completeness for a complexity class of operators. Then, several natural operators are proved to be complete for certain classes. For example, the operator that maps a polynomially length-related relation R to its domain (or, to its range) is complete for \(NP_{op}\); the operator that maps a polynomially length-bounded function f and a number x to the sum of all values f(y) with \(y\leq x\) is complete for {\#}P\({}_{op}\); and the operator that maps a polynomially length- related relation R to its transitive closure is complete for \(PSPACE_{op}\). One of the corollaries from these completeness results is that one-way functions exist iff \(P=U\), where U is the class of languages recognizable in polynomial time by a nondeterministic Turing machine with single accepting paths. This result was proved independently by \textit{J. Grollman} and \textit{A. Selman} [Proc. of 25th IEEE Symp. on Foundations of Computer Science, 495-503 (1984)].