The exhaustive-search conjecture for proofs of Kolmogorov randomness
Let be the set of Kolmogorov-random strings, and let be a proof-length bound for statements asserting that no proof of has length at most . Exhaustive-search conjecture. Conditional program logic and case-based reasoning are typically useless for ruling out length- proofs that ; consequently, the shortest proofs and fastest programs make no or limited use of such methods and rely primarily on exhaustive search. This is presented as a proposed explanation for the conjectured hardness of ruling out short proofs, not as an established consequence.
References
- Hunter Monroe, “Hardness of Ruling Out Short Proofs of Kolmogorov Randomness”, arXiv:2301.04789 (2023).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.