An exponential state lower bound for two-way nondeterministic complementation

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 $\frac{1}{2}{2}^{\lfloor (n-4)/127\rfloor }-1$ states.