Expressive power of witnessed symmetric choice
Choiceless polynomial time with counting is a language for computing on structures without choosing an arbitrary order. Witnessed symmetric choice permits a choice when the symmetry of its options can be certified. Does this extra operation define a property that the original language cannot express?
Why it matters and what counts as progress
Why it matters: The answer shows whether certified choices add expressive power when inputs have no distinguished order.
What counts as progress: Give an explicit query in the extended language and prove it has no expression in the original one. Specify the vocabulary, counting rules and number of choice operations.
How the problem developed
- 27 May 2022 · Witnessed symmetric choice [1]
Moritz Lichter and Pascal Schweitzer Introduced the witnessed-choice operator, using automorphisms to certify the symmetry of a choice set.
- 6 Oct 2026 · Reported expressivity separation [2]
OpenAI’s internal model A fixed sentence with one witnessed symmetric choice operator defines a Boolean query on all finite structures over a fixed eight-relation vocabulary that no choiceless polynomial time with counting sentence defines.
AI contribution
Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting
A fixed sentence with one witnessed symmetric choice operator defines a Boolean query on all finite structures over a fixed eight-relation vocabulary that no choiceless polynomial time with counting sentence defines.
Sources
Publication history
Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting
Daily emails by default, only when there’s an update.