← All problems

The exhaustive-search conjecture for proofs of Kolmogorov randomness

3 years old · traced to

Let RR be the set of Kolmogorov-random strings, and let tt be a proof-length bound for statements asserting that no proof of x∈Rx\in R has length at most tt. Exhaustive-search conjecture. Conditional program logic and case-based reasoning are typically useless for ruling out length-tt proofs that x∈Rx\in R; 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
  1. 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.