Collapsing Degrees (NOT KNOWN IF PUBLISHED BECAUSE AUTHOR HAS LEFT AT&T)

An m-degree is a collection of sets equivalent under Karp reductions (polynomial-time many-one reductions); for example the complete sets for NP or PSpace are m-degrees. An m-degree collapses if its members are (p-)isomorphic, i.e. equivalent under polynomial-time, 1-1, onto, polynomial-time invertible reductions.