Relativized isomorphisms of NP-complete sets
From MaRDI portal
Publication:687510
DOI10.1007/BF01200120zbMath0801.68065MaRDI QIDQ687510
Judy Goldsmith, Deborah Joseph
Publication date: 18 October 1993
Published in: Computational Complexity (Search for Journal in Brave)
isomorphisms; NP-completeness; complexity classes; collapsing degrees; relativized computation; sparse oracles
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Improved Merlin-Arthur protocols for central problems in fine-grained complexity, On quasilinear-time complexity theory, Time-space tradeoffs for satisfiability
Cites Work
- Unnamed Item
- Unnamed Item
- On one-way functions and polynomial-time isomorphisms
- Diagonalizations over polynomial time computable sets
- Collapsing degrees
- Are there interactive protocols for co-NP languages?
- One-way functions and the nonisomorphism of NP-complete sets
- The polynomial-time hierarchy and sparse oracles
- Bi-immune sets for complexity classes
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- The isomorphism conjecture fails relative to a random oracle
- Propositional representation of arithmetic proofs (Preliminary Version)
