Whether one-way functions (OWF) exist is arguably the most important problem in Cryptography, and beyond. While lots of candidate constructions of one-way functions are known, and recently also problems whose average-case hardness characterize the existence of OWFs have been demonstrated, the question of whether there exists some worst-case hard problem that characterizes the existence of one-way functions has remained open since their introduction in 1976. In this work, we present the first “OWF-complete” promise problem—a promise problem whose worst-case hardness w.r.t. \(\textsf{BPP}\) (resp. \(\mathsf{P/ poly}\) ) is equivalent to the existence of OWFs secure against \(\textsf{PPT}\) (resp. \(\textsf{nuPPT}\) ) algorithms. The problem is a variant of the Minimum Time-bounded Kolmogorov Complexity problem ( \(\textsf{MK}^{t}\textsf{P}[s]\) with a threshold s), where we condition on instances having small “computational depth”. We furthermore show that depending on the choice of the threshold s, this problem characterizes either “standard” (polynomially-hard) OWFs, or quasi polynomially- or subexponentially-hard OWFs. Additionally, when the threshold is sufficiently small (e.g., \(2^{O(\sqrt{\log n})}\) or \(\textsf{poly}\log n\) ) then sublinear hardness of this problem suffices to characterize quasi-poly-nomial/sub-exponential OWFs. While our constructions are black-box, our analysis is non-black box; we additionally demonstrate that fully black-box constructions of OWF from the worst-case hardness of this problem are impossible. We finally show that, under Rudich’s conjecture, and standard derandomization assumptions, our problem is not inside \(\textsf{coAM}\) ; as such, it yields the first candidate problem believed to be outside of \(\textsf{AM}\cap \textsf{coAM}\) , or even \(\textbf{SZK}\) , whose worst case hardness implies the existence of OWFs.