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 xRx\in R, let ConS+xR"(n)Con_{\mathcal{S}+“x\in R"}(n) denote the bounded consistency statement for the extension of S\mathcal{S} by the sentence encoding xRx\in R. Kolmogorov-random-string proof-size conjecture. Given S\mathcal{S}, there exists ϵ\epsilon such that, for all xRx\in R with xk|x|\geq k and for all nn, S\mathcal{S} requires 2n(1ϵ)2^{n(1-\epsilon)} symbols to prove ConS+xR"(n)Con_{\mathcal{S}+“x\in R"}(n).

Sources & referencesView supporting material

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.