Inverting onto functions.

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

zbMATH Keywords

nondeterministic polynomial-time Turing machines

Mathematics Subject Classification ID

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.