On one-way functions from NP-complete problems

DOI10.4230/LIPICS.CCC.2022.36MaRDI QIDQ6568379zbMATH OpenFDO

Authors Yanyi Liu, Rafael Pass

Publication date 5 July 2024

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2022.36

zbMATH Keywords

Kolmogorov complexityNP-completenessone-way functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(10)

• Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity
• Gap MCSP is not (Levin) NP-complete in obfustopia
• Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity
• NP-hardness of approximating meta-complexity: a cryptographic approach
• One-way functions and pKt complexity
• On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth
• Towards PNP from extended Frege lower bounds
• SAT reduces to the minimum circuit size problem with a random oracle
• Lower bounds on the overhead of indistinguishability obfuscation
• Kolmogorov complexity characterizes statistical zero knowledge

This page was built for publication: On one-way functions from NP-complete problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6568379)