Separating choiceless counting from polynomial time and witnessed choice
OpenAI research collection · 2 manuscripts · Source checked 2026-10-19
OpenAI's result summary
Confirms the Blass–Gurevich–Shelah noncapture conjecture: consistency of a linear system over 𝔽_(3) defines a polynomial-time query on unordered finite structures that choiceless polynomial time with counting cannot express. A separate result shows that adding witnessed symmetric choice strictly increases expressive power. Both separations hold for the full counting formalism, allowing hereditarily finite sets of arbitrary finite rank.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
Choiceless polynomial time with counting does not capture polynomial time
We prove that choiceless polynomial time with counting does not capture polynomial time on unordered finite structures, confirming the noncapture conjecture of Blass, Gurevich and Shelah. A linear-consistency query over 𝔽_(3) in a fixed binary vocabulary is decidable in polynomial time but not in the full counting formalism.
This PDF is listed in OpenAI's formalization catalogue. See the scope and dependencies before interpreting coverage.
Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting
We prove that witnessed symmetric choice strictly increases the expressive power of choiceless polynomial time with counting. A fixed sentence with one witnessed-choice occurrence defines a Boolean query on every finite input that is not definable in the original counting formalism.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.