Extremal dense hard-sequence conjecture for coTHEOREMS
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.