Extremal dense hard-sequence conjecture for coTHEOREMS

Let T\mathcal{T} be the theory used to define HH', and let HH' be the collection of dense sets of true T\mathcal{T}-unprovable sentences described in the source. Given a nondeterministic Turing machine MM accepting coTHEOREMS\texttt{coTHEOREMS}, consider inputs ϕi,1t\langle\phi_i,1^t\rangle with ii in a dense subset HMH'_M of HH'. Extremal dense hard-sequence conjecture. There exists such a dense subset HMH'_M, and for every sufficiently large x|x| depending on MM and T\mathcal{T}, MM requires 2t2^t steps for all tt on every input ϕi,1t\langle\phi_i,1^t\rangle with iHMi\in H'_M. This is presented as a stronger form of the preceding conjecture, asserting an exponential lower bound at every parameter tt 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

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.