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.
References
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
No solutions have been posted yet.