Inverting onto functions.
From MaRDI portal
Publication:1426007
DOI10.1016/S0890-5401(03)00119-6zbMath1058.68061OpenAlexW2044637393MaRDI QIDQ1426007
John D. Rogers, Ashish V. Naik, Stephen A. Fenner, Lance J. Fortnow
Publication date: 14 March 2004
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00119-6
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (12)
Nondeterministic functions and the existence of optimal proof systems ⋮ Comparing reductions to NP-complete sets ⋮ NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN ⋮ ON THE CIRCUIT-SIZE OF INVERSES ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ The shrinking property for NP and coNP ⋮ Recursion-theoretic ranking and compression ⋮ Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions ⋮ Total nondeterministic Turing machines and a p-optimal proof system for SAT ⋮ Does the polynomial hierarchy collapse if onto functions are invertible? ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ The opacity of backbones
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Sperner's lemma and robust machines
- On the complexity of the parity argument and other inefficient proofs of existence
- A taxonomy of complexity classes of functions
- Easy sets and hard certificate schemes
- 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
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- The isomorphism conjecture fails relative to a random oracle
- The Isomorphism Conjecture Holds Relative to an Oracle
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- The complexity of theorem-proving procedures
This page was built for publication: Inverting onto functions.