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

structural complexitycollapsing degreesp-isomorphismpolynomial degree

Mathematics Subject Classification ID

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

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

• 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?)
• A comparison of polynomial time reducibilities
• Creative sets
• Linear orderings under one-one reducibility
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On Simple Goedel Numberings and Translations
• On one-one polynomial time equivalence relations
• On one-way functions and polynomial-time isomorphisms
• On simple and creative sets in NP
• 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

(13)

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

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)