A Local Perspective on the Polynomial Hierarchy

We extend classical notions of computational complexity to the setting of distributed computing. Instead of a single computer, several networked computers communicate via synchronous message-passing to collectively solve some decision problem related to the network topology. Their running time is limited in two respects: 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 the computers, we obtain a generalization of the polynomial hierarchy (and hence of the complexity classes $\mathbf{P}$ and $\mathbf{NP}$). We then extend major 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. Moreover, perhaps 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. In contrast, a collapse of our hierarchy would have implied a collapse of the polynomial hierarchy.