Paper 2023/1765
The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False
Abstract
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
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. ITCS, ECCC
- Keywords
- function inversiontime-bounded Kolmogorov complexity
- Contact author(s)
-
noammaz @ gmail com
rafaelp @ tau ac il - History
- 2023-11-17: approved
- 2023-11-15: received
- See all versions
- Short URL
- https://ia.cr/2023/1765
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1765, author = {Noam Mazor and Rafael Pass}, title = {The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1765}, year = {2023}, url = {https://eprint.iacr.org/2023/1765} }