Collapsing degrees
From MaRDI portal
Publication:1109766
DOI10.1016/0022-0000(88)90007-4zbMath0656.03026OpenAlexW2293017760MaRDI QIDQ1109766
Stephen R. Mahaney, James S. Royer, Stuart A. Kurtz
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
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)
Related Items
One-way functions and the isomorphism conjecture, Isomorphisms and 1-L reductions, Polynomial-time axioms of choice and polynomial-time cardinality, Productive functions and isomorphisms, On p-creative sets and p-completely creative sets, On polynomial time one-truth-table reducibility to a sparse set, Relativized isomorphisms of NP-complete sets, On the power of parity polynomial time, On 1-truth-table-hard languages, Cook reducibility is faster than Karp reducibility in NP, Reductions in circuit complexity: An isomorphism theorem and a gap theorem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On one-one polynomial time equivalence relations
- Reductions among polynomial isomorphism types
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- On one-way functions and polynomial-time isomorphisms
- On simple and creative sets in NP
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- A comparison of polynomial time reducibilities
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- On Simple Goedel Numberings and Translations
- Linear orderings under one-one reducibility
- Creative sets
