  We study the complexity theory for the local distributed setting introduced
by Korman, Peleg and Fraigniaud. 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 languages 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 nondeterminism into the distributed setting by
the use of certificates and verifiers. The class NLD^#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 subset NLD subset NLD^#n.
  Our main contributions are strict hierarchies within the classes defined by
Korman, Peleg and Fraigniaud. 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
results are refined strict hierarchies within these nondeterministic classes.
