A survey of one-way functions in complexity theory
From MaRDI portal
Publication:4009812
DOI10.1007/BF01374525zbMath0749.68037OpenAlexW1970439855MaRDI QIDQ4009812
Publication date: 27 September 1992
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01374525
Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
A taxonomy of complexity classes of functions, One-way permutations and self-witnessing languages, An observation on associative one-way functions in complexity theory, A note on quadratic residuosity and UP, The isomorphism conjecture holds and one-way functions exist relative to an oracle, Tight lower bounds on the ambiguity of strong, total, associative, one-way functions, Unambiguous computations and locally definable acceptance types, Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions, NP-Creative sets: A new class of creative sets in NP, Strong polynomial-time reducibility, One-way permutations, computational asymmetry and distortion., Complexity classes of equivalence problems revisited, Function operators spanning the arithmetical and the polynomial hierarchy, If P \(\neq\) NP then some strongly noninvertible functions are invertible, A hierarchy based on output multiplicity, Reductions in circuit complexity: An isomorphism theorem and a gap theorem, Characterizing the existence of one-way permutations, Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory, On characterizing the existence of partial one-way permutations
Cites Work
- Unnamed Item
- On some natural complete operators
- On one-one polynomial time equivalence relations
- Reductions among polynomial isomorphism types
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- On one-way functions and polynomial-time isomorphisms
- The complexity of optimization problems
- Relative complexity of checking and evaluating
- Riemann's hypothesis and tests for primality
- Positive Relativizations of Complexity Classes
- Complexity Measures for Public-Key Cryptosystems
- Natural Self-Reducible Sets
- Completeness, Approximation and Density
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Polynomial Time Enumeration Reducibility
- The isomorphism conjecture fails relative to a random oracle
- Recursively enumerable sets of positive integers and their decision problems
- Creative sets
