Separating choiceless counting from polynomial time and witnessed choice
What the paper claims, in its own words
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.
The plain-language explainer for this entry is still coming.
The original papers (2)
- Choiceless polynomial time with counting does not capture polynomial time (PDF, opens in a new tab) September 23, 2026 Formal proof listed
- Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting (PDF, opens in a new tab) September 24, 2026