Extremal dense hard-sequence conjecture for coTHEOREMS
Extremal dense hard-sequence conjecture for coTHEOREMS
Let be the theory used to define , and let be the collection of dense sets of true -unprovable sentences described in the source. Given a nondeterministic Turing machine accepting , consider inputs with in a dense subset of . Extremal dense hard-sequence conjecture. There exists such a dense subset , and for every sufficiently large depending on and , requires steps for all on every input with . This is presented as a stronger form of the preceding conjecture, asserting an exponential lower bound at every parameter and strengthening the proposed explanation for the absence of optimal proof systems.
Sources & referencesView supporting material
Primary source
Hunter Monroe, “Average-Case Hardness of Proving Tautologies and Theorems”, arXiv:2205.07803 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.