2026-07-24T12:59:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19608 2024-03-06T11:04:28Z ddc:004 open_access

The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity Is False Mazor, Noam Pass, Rafael Kolmogorov complexity perebor conjecture function inversion The Perebor (Russian for "brute-force search") conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP ≠ P conjecture (which they predate) and state that for "meta-complexity" problems, such as the Time-bounded Kolmogorov complexity Problem, and the Minimum Circuit Size Problem, there are no better algorithms than brute force search. In this paper, we disprove the non-uniform version of the Perebor conjecture for the Time-Bounded Kolmogorov complexity problem. We demonstrate that for every polynomial t(⋅), there exists of a circuit of size 2^{4n/5+o(n)} that solves the t(⋅)-bounded Kolmogorov complexity problem on every instance. Our algorithm is black-box in the description of the Universal Turing Machine U employed in the definition of Kolmogorov Complexity and leverages the characterization of one-way functions through the hardness of the time-bounded Kolmogorov complexity problem of Liu and Pass (FOCS'20), and the time-space trade-off for one-way functions of Fiat and Naor (STOC'91). We additionally demonstrate that no such black-box algorithm can have circuit size smaller than 2^{n/2-o(n)}. Along the way (and of independent interest), we extend the result of Fiat and Naor and demonstrate that any efficiently computable function can be inverted (with probability 1) by a circuit of size 2^{4n/5+o(n)}; as far as we know, this yields the first formal proof that a non-trivial circuit can invert any efficient function. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noam Mazor and Rafael Pass 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.80 urn:nbn:de:0030-drops-196088 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.80 eng https://creativecommons.org/licenses/by/4.0/legalcode