Dense hard-sequence conjecture for true unprovable coTHEOREMS
Dense hard-sequence conjecture for true unprovable coTHEOREMS
Let be the set comprising and other dense sets of true sentences unprovable in , including the specified sets associated with universal Turing machines and Turing jumps. For a nondeterministic Turing machine accepting , let denote the th arithmetic sentence in the relevant enumeration. Dense hard-sequence conjecture. There is a dense subset of such that if and only if is a hard sequence for . The conjecture identifies dense hard sequences arising from true unprovable sentences and would imply that has dense hard sequences; the source notes that 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
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.