Constant-depth Frege oddtown conjecture for nontrivial prime moduli
Constant-depth Frege oddtown conjecture for nontrivial prime moduli
Let be the depth- fragment of Frege, let be the oddtown axiom scheme, and let be the modular counting principle modulo . For a proof system , write when each formula has a polynomial-size -proof.
Constant-depth Frege oddtown conjecture. For each and each prime ,
The preceding result establishes the converse direction for powers of at the level of . This conjecture strengthens the proposed separation to constant-depth Frege proof size; the paper does not prove it in full.
Sources & referencesView supporting material
Primary source
Eitetsu Ken, “On some Σ^B_0-formulae generalizing counting principles over V^0”, arXiv:2203.10237 (2024).
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.