Hierarchies in Local Distributed Decision
Friedhelm Meyer auf der Heide, Kamil Swirkot · 2013
We study the complexity theory for the local distributed setting introduced by Korman, Peleg and Fraigniaud in their seminal paper [3]. They have defined three complexity classes LD (Local Decision), NLD (Nondeterministic Local Decision) and NLD#n. The class LD consists of all languages which can be decided with a constant number of communication rounds. The class NLD consists of all lan-guages which can be verified by a nondeterministic algorithm with a constant number of communication rounds. In order to define the nondeterministic classes, they have transferred the notation of nondeter-minism into the distributed setting by the use of certificates and verifiers. The classNLD#n consists of all languages which can be verified by a nondeterministic algorithm where each node has access to an oracle for the number of nodes. They have shown the hierarchy LD ( NLD ( NLD#n. Our main contributions are strict hierarchies within the classes defined by Korman, Peleg and Fraig-niaud. We define additional complexity classes: the class LD(t) consists of all languages which can be decided with at most t communication rounds. The class NLD(O(f)) consists of all languages which can be verified by a local verifier such that the size of the certificates that are needed to verify the language are bounded by a function from O(f). Our main result is the following hierarchy within the nondeterministic classes: LD ( NLD(O(1)) ( NLD(O(log n)) ( NLD(O(n)) ( NLD(O(n2)) ⊆ NLD(O(n2 + |w|)) = NLD. In order to prove this hierarchy, we give several lower bounds on the sizes of certificates that are needed to verify some languages from NLD. For the deterministic classes we prove the following hierarchy: