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