ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.