Nondiamond theorems for polynomial time reducibility (Q1201882): Difference between revisions

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.