2024/04/24 by Tuhin Sahai, Sahai, Tuhin, Abeynaya Gnanasekaran +1
Economics, Econometrics and Finance · Mathematics · Physics and Astronomy · #Computational Complexity (cs.CC) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Dynamics and Fractals #Numerical Analysis (math.NA) #Quantum chaos and dynamical systems #Stochastic processes and financial applications
paper · pdf · doi:10.48550/arxiv.2404.16024
openalex publication_date 2024/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Unique Games Conjecture (UGC) constitutes a highly dynamic subarea within computational complexity theory, intricately linked to the outstanding P versus NP problem. Despite multiple insightful results in the past few years, a proof for the conjecture remains elusive. In this work, we construct a novel dynamical systems-based approach for studying unique games and, more generally, the field of computational complexity. We propose a family of dynamical systems whose equilibria correspond to solutions of unique games and prove that unsatisfiable instances lead to ergodic dynamics. Moreover, as the instance hardness increases, the weight of the invariant measure in the vicinity of the optimal assignments scales polynomially, sub-exponentially, or exponentially depending on the value gap. We numerically reproduce a previously hypothesized hardness plot associated with the UGC. Our results indicate that the UGC is likely true, subject to our proposed conjectures that link dynamical systems theory with computational complexity.