  The advice complexity of an online problem is a measure of how much knowledge
of the future an online algorithm needs in order to achieve a certain
competitive ratio. Using advice complexity, we define the first online
complexity class, AOC. The class includes independent set, vertex cover,
dominating set, and several others as complete problems. AOC-complete problems
are hard, since a single wrong answer by the online algorithm can have
devastating consequences. For each of these problems, we show that
$\log\left(1+(c-1)^{c-1}/c^{c}\right)n=\Theta (n/c)$ bits of advice are
necessary and sufficient (up to an additive term of $O(\log n)$) to achieve a
competitive ratio of $c$.
  The results are obtained by introducing a new string guessing problem related
to those of Emek et al. (TCS 2011) and B\"ockenhauer et al. (TCS 2014). It
turns out that this gives a powerful but easy-to-use method for providing both
upper and lower bounds on the advice complexity of an entire class of online
problems, the AOC-complete problems.
  Previous results of Halld\'orsson et al. (TCS 2002) on online independent
set, in a related model, imply that the advice complexity of the problem is
$\Theta (n/c)$. Our results improve on this by providing an exact formula for
the higher-order term. For online disjoint path allocation, B\"ockenhauer et
al. (ISAAC 2009) gave a lower bound of $\Omega (n/c)$ and an upper bound of
$O((n\log c)/c)$ on the advice complexity. We improve on the upper bound by a
factor of $\log c$. For the remaining problems, no bounds on their advice
complexity were previously known.
