Nondiamond theorems for polynomial time reducibility

DOI10.1016/0022-0000(92)90032-EMaRDI QIDQ1201882zbMATH OpenFDO

Authors Rodney G. Downey

Publication date 17 January 1993

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)90032-E

zbMATH Keywords

minimal pairs recursion theory reducibility

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

Given any type of reducibility one can define the degrees relative to that reduction type as the equivalence classes, where \(A\) and \(B\) are equivalent if and only if \(A\) is reducible to \(B\) and \(B\) is reducible to \(A\). In both the cases of polynomial time many-one or polynomial time Turing reducibility the class of polynomial time computable sets builds the unique minimal element in the degree structure. A diamond in the degree structure for a reduction type is a triple of degrees \(a\), \(b\), and \(c\), such that the only sets reducible to \(a\)-sets as well as to \(b\)-sets are the \(p\)-time sets, and \(c\) is the lowest degree of sets \(C\) such that all sets of \(a\) and \(b\) can be reduced to \(C\). In this case, \(c\) is called the top of the diamond. The main result of the article states that there are degrees relative to polynomial time Turing reducibility being not the top of any diamond, thus extending a result of \textit{K. Ambos-Spies} [An extension of the non-diamond theorem in classical and alpha-recursion theory, Univ. Dortmund (1982; Zbl 0533.03026)] who showed the same for polynomial time many-one reducibility.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Nondiamond theorems for polynomial time reducibility

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