On one-way functions and polynomial-time isomorphisms
From MaRDI portal
Publication:1097694
DOI10.1016/0304-3975(86)90152-0zbMath0635.68038OpenAlexW2078503376MaRDI QIDQ1097694
Ding-Zhu Du, Timothy J. Long, Ker-I. Ko
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(86)90152-0
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items (21)
One-way functions and the isomorphism conjecture ⋮ Collapsing degrees via strong computation ⋮ DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization ⋮ The isomorphism conjecture holds and one-way functions exist relative to an oracle ⋮ On P-immunity of exponential time complete sets ⋮ Collapsing degrees ⋮ Mathematical problems in cryptology ⋮ A survey of one-way functions in complexity theory ⋮ A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality ⋮ Complete problems and strong polynomial reducibilities ⋮ The degree structure of 1-L reductions ⋮ Productive functions and isomorphisms ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ On p-creative sets and p-completely creative sets ⋮ On polynomial time one-truth-table reducibility to a sparse set ⋮ Relativized isomorphisms of NP-complete sets ⋮ On the power of parity polynomial time ⋮ On 1-truth-table-hard languages ⋮ Cook reducibility is faster than Karp reducibility in NP ⋮ Reductions in circuit complexity: An isomorphism theorem and a gap theorem ⋮ On one-one polynomial time equivalence relations
Cites Work
This page was built for publication: On one-way functions and polynomial-time isomorphisms
