  We extend classical methods of computational complexity to the setting of
distributed computing, where they are sometimes more effective than in their
original context. Our focus is on distributed decision in the LOCAL model,
where multiple networked computers communicate via synchronous message-passing
to collectively answer a question about their network topology. Rather
unusually, we impose two orthogonal constraints on the running time of this
model: the number of communication rounds is bounded by a constant, and the
number of computation steps of each computer is polynomially bounded by the
size of its local input and the messages it receives.
  By letting two players take turns assigning certificates to all computers in
the network, we obtain a generalization of the polynomial hierarchy (and hence
of the complexity classes $\mathbf{P}$ and $\mathbf{NP}$). We then extend some
key results of complexity theory to this setting, in particular the Cook-Levin
theorem (which identifies Boolean satisfiability as a complete problem for
$\mathbf{NP}$), and Fagin's theorem (which characterizes $\mathbf{NP}$ as the
problems expressible in existential second-order logic). The original results
can be recovered as the special case where the network consists of a single
computer. But perhaps more surprisingly, the task of separating complexity
classes becomes easier in the general case: we can show that our hierarchy is
infinite, while it remains notoriously open whether the same is true in the
case of a single computer. (By contrast, a collapse of our hierarchy would have
implied a collapse of the polynomial hierarchy.) As an application, we propose
quantifier alternation as a new approach to measuring the locality of problems
in distributed computing.
