{"id":"openai-math/An-exponential-state-lower-bound-for-two-way-nondeterministic-complementation","pdf":"https://github.com/openai/math/blob/main/preprints/An-exponential-state-lower-bound-for-two-way-nondeterministic-complementation-September-25-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/An-exponential-state-lower-bound-for-two-way-nondeterministic-complementation-September-25-2026","tags":["automata-theory","computational-complexity"],"score":0,"title":"An exponential state lower bound for two-way nondeterministic complementation","domain":"Theoretical computer science","family":"129","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We prove that two-way nondeterministic finite automata cannot be complemented with a polynomial number of states independent of the alphabet. For each n ≥ 4 we construct an n -state automaton over a finite alphabet whose complement requires at least $`\\tfrac12 2^{\\lfloor(n-4)/127\\rfloor}-1`$ states.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{},"formalized":true,"family_title":"Exponential state costs for two-way automata"}