The complexity types of computable sets

DOI10.1016/0022-0000(92)90018-EMaRDI QIDQ1190982zbMATH OpenFDO

Authors Wolfgang Maass, Theodore A. Slaman

Publication date 27 September 1992

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(92)90018-E

completeness random access machines reducibility

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

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}\)).

Recommendations

Cites work

Cited in

(7)

This page was built for publication: The complexity types of computable sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1190982)