Revised: November 3, 2016

Published: November 29, 2016

**Keywords:**nondeterminism, distributed computing, locality, graphs

**ACM Classification:**C.2.4, F.1.3

**AMS Classification:**68M14, 68Q15, 68Q25, 68Q85, 03F20

**Abstract:**
[Plain Text Version]

We study *decision problems* related to *graph
properties* from the perspective of *nondeterministic
distributed algorithms*. For a *yes*-instance there must
exist a *proof* that can be verified with a distributed
algorithm: all nodes must accept a valid proof, and at least one
node must reject an invalid proof. We focus on *locally
checkable proofs* that can be verified with a constant-time
distributed algorithm. For example, it is easy to prove that a
graph is bipartite: the locally checkable proof gives a
$2$-coloring of the graph, which only takes $1$ bit per
node. However, it is more difficult to prove that a graph is
*not* bipartite—it turns out that any locally checkable
proof requires $\Omega(\log n)$ bits per node.

In this paper we classify graph properties according to their
local proof complexity, i.e., how many bits per node are needed
in a locally checkable proof. We establish tight or near-tight
results for classical graph properties such as the chromatic
number. We show that the local proof complexities form a natural
hierarchy of complexity classes: for many classical graph
properties, the local proof complexity is either $0$, $\Theta(1)$,
$\Theta(\log n)$, or $\text{poly}(n)$ bits per node. Among the most
difficult graph properties are proving that a graph is symmetric
(has a non-trivial automorphism), which requires $\Omega(n^2)$
bits per node, and proving that a graph is *not*
$3$-colorable, which requires $\Omega(n^2/\log n)$ bits per
node. Any property of connected graphs admits a trivial proof with
$O(n^2)$ bits per node.

A preliminary version of this paper appeared in the Proceedings of the 30th ACM Symposium on Principles of Distributed Computing (PODC 2011).