Separating choiceless counting from polynomial time and witnessed choice

Formal proof listed 2 papers September 23, 2026
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)