Collapsing Polynomial-Time Degrees
Klaus Ambos‐Spies, Levke Bentzien, Peter A. Fejer, Wolfgang Merkle, Frank Stephan · Cambridge University Press eBooks · 2017
For reducibilities r and r 0 such that r is weaker than r 0 , we say that the r-degree of A, i.e., the class of sets which are r-equivalent to A, collapses to the r 0 -degree of A if both degrees coincide. We investigate for the polynomial-time bounded many-one, bounded truth-table, truthtable, and Turing reducibilities whether and under which conditions such collapses can occur. While we show that such collapses do not occur for sets which are hard for exponential time, we have been able to construct a recursive set such that its bounded truth-table degree collapses to its many-one degree. The question whether there is a set such that its Turing degree collapses to its many-one degree is still open; however, we show that such a set -- if it exists -- must be recursive.