The complexity types of computable sets (Q1190982)

The authors study a refinement of the time complexity classes for RAMs. They define an equivalence relation \(A=_ C B\Leftrightarrow\text{ (for all time constructible } f: A\in DTIME(f)\Leftrightarrow B\in DTIME(f))\). The \(=_ C\)-equivalence class of \(A\) is called its complexity type. By a refinement of Blum's speed-up-theorem the authors characterize complexity types with the help of cofinal sequences of time bounds. This elegant and sharp characterization is the main tool for all later proofs, but it is also interesting in its own right. As a direct corollary of their characterization they observe that every complexity type contains a sparse set and that the complexity types with the partial order \(\leq_ C\) form a lattice. Then they consider the relationship with polynomial time reducibility. By combining their basic constructions with Ladner-type ``looking back'' techniques they prove that every complexity type \({\mathcal C}\not\subseteq P\) contains sets \(A\) and \(B\) that are incomparable with regard to polynomial time reductions. With the help of a more complicated technique (that has been developed by \textit{K. Ambos-Spies} [Lect. Notes Comput. Sci. 270, 1-3 (1987; Zbl 0637.03038)]\ and independently by \textit{J. Shinoda} and \textit{T. A. Slaman} [J. Comp. Syst. Sci. 41, 321-366 (1990; Zbl 0715.68040)]\ they construct a complexity type which contains sets \(A\) and \(B\) that form a minimal pair. It is stated as an open question whether every complexity type \({\mathcal C}\not\subseteq P\) contains a minimal pair. Finally they consider the structure of complexity types inside \(P\). For this investigation the class of admissible time bounds is further restricted in such a way that each complexity type of closed under linear time Turing equivalence. With these modifications it is shown that a complexity \({\mathcal C}\subseteq P\) contains a complete set with respect to linear time many-one reduction iff \({\mathcal C}\) is principal (i.e. there is an optimal time bound that characterizes \({\mathcal C}\)).