{"id":"openai-math/Witnessed-symmetric-choice-is-strictly-stronger-than-choiceless-polynomial-time-with-counting","pdf":"https://github.com/openai/math/blob/main/preprints/Witnessed-symmetric-choice-is-strictly-stronger-than-choiceless-polynomial-time-with-counting-September-24-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Witnessed-symmetric-choice-is-strictly-stronger-than-choiceless-polynomial-time-with-counting-September-24-2026","tags":["finite-model-theory","logic","complexity-theory"],"score":0,"title":"Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting","domain":"Mathematical logic","family":"243","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"math.LO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":false,"family_title":"Separating choiceless counting from polynomial time and witnessed choice"}