Progress on Collapsing Degrees Extended Abstract
Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer · 1987
Berman and Hartmanis conjectured that the m-degree of NP complete sets collapses. (An m-degree is a collection of sets equivalent under polynomial-time many-one reductions. An m-degree collapses iff all of the sets in the m-degree are pairwise p-isomorphic, i.e., any two sets are equivalent by polynomial-time many-one reductions that are one-one, onto and polynomial-time invertible.) Recent work has treated the conjecture more broadly and shown the existence of collapsing m-degrees and, indeed, exhibited both collapsing and noncollapsing m-degrees that are 2-tt complete for EXP. This paper shows that recent constructions of collapsing degrees and noncollapsing degrees in EXP can be extended to: • PSPACE for Cogspace reducibilities and isomorphisms; •$\mathop \Sigma olimits_2^{\rm P}$for O(nk)-time reducibilities and O(nk+1)-time isomorphism; and • 2-tt complete sets in NPAfor polynomial-time reducibilities for a sparse oracle A. We also introduce a new technique for transformation of certain exponential-time diagonalizations into relativized NP constructions. Finally, we examine several areas of continuing research problems: these questions range from establishing collapsing for complete degrees, and special problems encountered with classes not closed under complementation, to relativization.