Dense hard-sequence conjecture for true unprovable coTHEOREMS

About 4 years old · traced to

Let H′H' 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 HM′H'_M of H′H' such that i∈HM′i\in H'_M if and only if (⟨ϕi,1t⟩)t∈N(\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 H′H' and the associated notion of balance may not be fully well defined.

References

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.