A Time Hierarchy Theorem for the LOCAL Model

2017/04/20 by Yi‐Jun Chang, Seth Pettie, Chang, Yi-Jun +1 · 5 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1704.06297

openalex publication_date 2017/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem holds in the distributed LOCAL model has been open for many years. It is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as O(1),O(log^* n), O(log n), 2^{O(√(log n))}, etc. In this paper we establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy. 1. We define an infinite set of simple coloring problems called Hierarchical 2(1)/(2)-Coloring. A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the k-level Hierarchical 2(1)/(2)-Coloring problem is Θ(n^1/k), for k∈ℤ⁺. The upper and lower bounds hold for both general graphs and trees, and for both randomized and deterministic algorithms. 2. Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem that states that any randomized n^o(1)-time algorithm solving the LCL can be transformed into a deterministic O(log n)-time algorithm. Together with a previous result, this establishes that on trees, there are no natural deterministic complexities in the ranges ω(log^* n)---o(log n) or ω(log n)---n^o(1). 3. We expose a gap in the randomized time hierarchy on general graphs. Any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in O(T_LLL) time, which is the complexity of the distributed Lovasz local lemma problem, currently known to be Ω(loglog n) and O(log n).

Cited by

• On the Complexity of Distributed Edge Coloring and Orientation Problems
• A Post-Quantum Lower Bound for the Distributed Lovasz Local Lemma.
• Faster Distributed Δ-Coloring via a Reduction to MIS
• Distributed Algorithms for Potential Problems
• New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs

Related

• Sublogarithmic Distributed Algorithms for Lov 'asz Local lemma, and the\n Complexity Hierarchy
• Almost Global Problems in the LOCAL Model
• The randomized local computation complexity of the Lovász local lemma
• New Classes of Distributed Time Complexity
• An Automatic Speedup Theorem for Distributed Problems