Dense hard-sequence conjecture for true unprovable coTHEOREMS

Let HH' be the set comprising HH and other dense sets of true sentences unprovable in T\mathcal{T}, including the specified sets associated with universal Turing machines and Turing jumps. For a nondeterministic Turing machine MM accepting coTHEOREMS\texttt{coTHEOREMS}, let ϕi\phi_i denote the iith arithmetic sentence in the relevant enumeration. Dense hard-sequence conjecture. There is a dense subset HMH'_M of HH' such that iHMi\in H'_M if and only if (ϕi,1t)tN(\langle\phi_i,1^t\rangle)_{t\in\mathbb{N}} is a hard sequence for MM. The conjecture identifies dense hard sequences arising from true unprovable sentences and would imply that coTHEOREMS\texttt{coTHEOREMS} has dense hard sequences; the source notes that HH' and the associated notion of balance may not be fully well defined.

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.