Kolmogorov-random-string consistency proof-size conjecture

Let RR be the set of Kolmogorov-random binary strings defined using the fixed universal Turing machine UU, and let kk be the threshold supplied by Chaitin's incompleteness theorem for the theory S\mathcal{S}. For x∈Rx\in R, let ConS+“x∈R"(n)Con_{\mathcal{S}+“x\in R"}(n) denote the bounded consistency statement for the extension of S\mathcal{S} by the sentence encoding x∈Rx\in R. Kolmogorov-random-string proof-size conjecture. Given S\mathcal{S}, there exists ϵ\epsilon such that, for all x∈Rx\in R with ∣x∣≥k|x|\geq k and for all nn, S\mathcal{S} requires 2n(1−ϵ)2^{n(1-\epsilon)} symbols to prove ConS+“x∈R"(n)Con_{\mathcal{S}+“x\in R"}(n).

References

Primary source

Hunter Monroe, “A Proposed Characterization of p-Simulation Between Theories”, arXiv:2507.13576 (2026).

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.