One-way functions and the nonisomorphism of NP-complete sets

DOI10.1016/0304-3975(91)90323-TzbMath0718.03031OpenAlexW1977930625MaRDI QIDQ2639055

Juris Hartmanis, Hemaspaandra, Lane A.

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90323-t

zbMATH Keywords

one-way functionsNP-complete setsOne-way Conjecturerelativized counterexample

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items

Exact lower time bounds for computing Boolean functions on CREW PRAMs, Collapsing degrees via strong computation, The isomorphism conjecture holds and one-way functions exist relative to an oracle, A tight relationship between generic oracles and type-2 complexity theory, Promise problems and access to unambiguous computation, On (simple) decision tree rank, Time and space complexity of deterministic and nondeterministic decision trees, An oracle builder's toolkit, A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$, Non-uniform reductions, Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives, On sets polynomially enumerable by iteration, Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions, UP and the low and high hierarchies: A relativized separation, NP-Creative sets: A new class of creative sets in NP, Separating complexity classes with tally oracles, Relativized isomorphisms of NP-complete sets, On the power of parity polynomial time, LWPP and WPP are not uniformly gap-definable, The relative complexity of NP search problems

Cites Work

• On one-one polynomial time equivalence relations
• Reductions among polynomial isomorphism types
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Isomorphisms and 1-L reductions
• Complexity classes without machines: on complete languages for UP
• Relative complexity of checking and evaluating
• Complexity Measures for Public-Key Cryptosystems
• Relativized Questions Involving Probabilistic Algorithms
• Complete Problems and Strong Polynomial Reducibilities
• 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