Collapsing degrees

DOI10.1016/0022-0000(88)90007-4MaRDI QIDQ1109766zbMATH OpenOpenAlexFDO

Authors Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Publication date 1988

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(88)90007-4

zbMATH Keywords

collapsing degreesp-isomorphismpolynomial degreestructural complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• Publication:4944898
• scientific article; zbMATH DE number 176750
• scientific article; zbMATH DE number 782046
• Relativized isomorphisms of NP-complete sets
• Collapsing degrees via strong computation

Cites work

• A comparison of polynomial time reducibilities
• Creative sets
• scientific article; zbMATH DE number 3117565 (Why is no real title available?)
• scientific article; zbMATH DE number 3909741 (Why is no real title available?)
• scientific article; zbMATH DE number 3909745 (Why is no real title available?)
• scientific article; zbMATH DE number 3984574 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3594673 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3186858 (Why is no real title available?)
• Linear orderings under one-one reducibility
• On Isomorphisms and Density of NP and Other Complete Sets
• On one-one polynomial time equivalence relations
• On one-way functions and polynomial-time isomorphisms
• On simple and creative sets in NP
• On Simple Goedel Numberings and Translations
• Reductions among polynomial isomorphism types
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)

Cited in

(14)

• On one-one polynomial time equivalence relations
• Isomorphisms and 1-L reductions
• On p-creative sets and p-completely creative sets
• On polynomial time one-truth-table reducibility to a sparse set
• On 1-truth-table-hard languages
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• One-way functions and the isomorphism conjecture
• Collapsing degrees via strong computation
• Productive functions and isomorphisms
• scientific article; zbMATH DE number 1420830 (Why is no real title available?)
• On the power of parity polynomial time
• Polynomial-time axioms of choice and polynomial-time cardinality
• Relativized isomorphisms of NP-complete sets
• Cook reducibility is faster than Karp reducibility in NP

This page was built for publication: Collapsing degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109766)