Locally Checkable Proofs in Distributed Computing
Locally Checkable Proofs in Distributed Computing
复制标题
DOI：
10.4086/toc.2016.v012a019
复制
发表时间：
2016-01-01
影响因子：
1
通讯作者：
Suomela, Jukka
中科院分区：
文献类型：
--
作者：
Goeoes, Mika;Suomela, Jukka
我们从非确定性分布式算法的角度研究与图的属性相关的决策问题。对于一个yes实例，必须存在一个可以用分布式算法验证的证明：所有节点必须接受一个有效的证明，并且至少有一个节点必须拒绝一个无效的证明。我们专注于本地可检查的证明，可以验证一个恒定的时间分布式算法。例如，证明一个图是二分图很容易：局部可检验证明给出了图的2-着色，每个节点只需要1位。然而，要证明一个图不是二分图就比较困难了--事实证明，任何局部可检验的证明都需要每个节点有Omega（logn）位。在本文中，我们根据图的局部证明复杂度对图的性质进行了分类，即，在本地可检验证明中每个节点需要多少比特。我们建立紧或近紧的结果，经典的图形属性，如色数。我们表明，本地证明复杂性形成一个自然的复杂性等级：对于许多经典的图形属性，本地证明复杂性是0，Theta（1），Theta（logn），或poly（n）位每节点。最困难的图形属性之一是证明一个图是对称的（具有非平凡的自同构），这需要每个节点的Omega（n（2））位，并证明一个图是不可3-着色的，这需要每个节点的Omega（n（2）/logn）位。连通图的任何性质都可以用O（n（2））比特证明。
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(logn) 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(logn), 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)/logn) bits per node. Any property of connected graphs admits a trivial proof with O(n(2)) bits per node.