What can be verified locally?

作者：

Highlights：

• We build a hierarchy of complexity classes in the distributed LOCAL model.

• Perhaps surprisingly, we show that this hierarchy collapses at the second level.

• We provide complete problems for most of the classes.

摘要

•We build a hierarchy of complexity classes in the distributed LOCAL model.•Perhaps surprisingly, we show that this hierarchy collapses at the second level.•We provide complete problems for most of the classes.

论文关键词：Distributed computing,Decision problems,Local model

论文评审过程：Received 25 September 2017, Revised 14 May 2018, Accepted 25 May 2018, Available online 13 August 2018, Version of Record 13 August 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.05.004