Collapsing degrees
DOI10.1016/0022-0000(88)90007-4zbMATH Open0656.03026OpenAlexW2293017760MaRDI QIDQ1109766FDOQ1109766
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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- On one-way functions and polynomial-time isomorphisms
- A comparison of polynomial time reducibilities
- Title not available (Why is that?)
- Title not available (Why is that?)
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
- On one-one polynomial time equivalence relations
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Creative sets
- Title not available (Why is that?)
- Linear orderings under one-one reducibility
- Reductions among polynomial isomorphism types
- On Simple Goedel Numberings and Translations
- On simple and creative sets in NP
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (13)
- On one-one polynomial time equivalence relations
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem
- On p-creative sets and p-completely creative sets
- 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
- Title not available (Why is that?)
- Isomorphisms and 1-L reductions
- On the power of parity polynomial time
- Relativized isomorphisms of NP-complete sets
- On polynomial time one-truth-table reducibility to a sparse set
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)
