Collapsing degrees (Q1109766): Difference between revisions

An m-degree is an equivalence class under polynomial-time many-one reductions. An m-degree is said to be collapsing if its members are p- isomorphic. This notion stems from the well-known conjecture of Berman and Hartmanis, which asserts that all NP-complete sets are p-isomorphic. Much work has been centered around this conjecture and both ``pro'' and ``con'' facts emerged (see the introduction of this paper for an excellent, clear and concise survey of these matters). The paper is a valuable contribution in this area of structural complexity. It provides the first examples of collapsing degrees. Thus it is shown that, for each set A, there is a collapsing degree which is m-hard for A. Also, a collapsing degree which is 2-tt complete for EXP is constructed.