  The precise complexity of complementing B\"uchi automata is an intriguing and
long standing problem. While optimal complementation techniques for finite
automata are simple - it suffices to determinize them using a simple subset
construction and to dualize the acceptance condition of the resulting automaton
- B\"uchi complementation is more involved. Indeed, the construction of an
EXPTIME complementation procedure took a quarter of a century from the
introduction of B\"uchi automata in the early 60s, and stepwise narrowing the
gap between the upper and lower bound to a simple exponent (of (6e)n for
B\"uchi automata with n states) took four decades. While the distance between
the known upper (O'(0.96 n)n') and lower ('(0.76 n)n') bound on the required
number of states has meanwhile been significantly reduced, an exponential
factor remains between them. Also, the upper bound on the size of the
complement automaton is not linear in the bound of its state space. These gaps
are unsatisfactory from a theoretical point of view, but also because B\"uchi
complementation is a useful tool in formal verification, in particular for the
language containment problem. This paper proposes a B\"uchi complementation
algorithm whose complexity meets, modulo a quadratic (O(n2)) factor, the known
lower bound for B\"uchi complementation. It thus improves over previous
constructions by an exponential factor and concludes the quest for optimal
B\"uchi complementation algorithms.
