Theory of Computing
-------------------
Title : Locally Checkable Proofs in Distributed Computing
Authors : Mika Goos and Jukka Suomela
Volume : 12
Number : 19
Pages : 1-33
URL : http://www.theoryofcomputing.org/articles/v012a019
Abstract
--------
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 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)
(DOI: 10.1145/1993806.1993829)