We present the first natural NP-complete problem whose average-case hardness w.r.t. the uniform distribution over instances is equivalent to the existence of one-way functions (OWFs). The problem, which originated in the 1960s, is the Conditional Time-Bounded Kolmogorov Complexity Problem: let $K^t(x | z)$ be the length of the shortest “program” that, given the “auxiliary input” $z$, outputs the string $x$ within time $t(|x|)$, and let
McKTP$[t,zeta]$ be the set of strings $(x,z,k)$ where $|z| = zeta(|x|)$, $|k| = log |x|$ and $K^t(x | z)

By admin