scientific article; zbMATH DE number 4779

MaRDI QIDQ4712666zbMATH OpenFDO

Authors Yuri Gurevich

Publication date 25 June 1992

zbMATH Keywords

\(P=?NP\)\(P\) time computable distributionsdomination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(8)

• Average case completeness
• Polynomial time samplable distributions
• On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
• One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions
• Reductions and convergence rates of average time
• On one-way functions and sparse languages
• Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity
• On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth

This page was built for publication:

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