A hierarchy based on output multiplicity
From MaRDI portal
Publication:1274991
DOI10.1016/S0304-3975(98)00060-7zbMath0912.68043OpenAlexW2052403496MaRDI QIDQ1274991
John D. Rogers, Ashish V. Naik, James S. Royer, Selman, Alan L.
Publication date: 12 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00060-7
Related Items
Nondeterministic functions and the existence of optimal proof systems ⋮ The Shrinking Property for NP and coNP ⋮ The shrinking property for NP and coNP ⋮ The consequences of eliminating NP solutions ⋮ Reducing the number of solutions of NP functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On self-reducibility and weak P-selectivity
- Hard promise problems and nonuniform complexity
- A taxonomy of complexity classes of functions
- Functions computable with limited access to NP
- The isomorphism conjecture holds and one-way functions exist relative to an oracle
- An oracle builder's toolkit
- The complexity of promise problems with applications to public-key cryptography
- Quantitative Relativizations of Complexity Classes
- Complexity Measures for Public-Key Cryptosystems
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- A survey of one-way functions in complexity theory
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- The isomorphism conjecture fails relative to a random oracle
- Oracles That Compute Values
- The Isomorphism Conjecture Holds Relative to an Oracle
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
