The exhaustive-search conjecture for proofs of Kolmogorov randomness
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.