Proving nphardness of 4to1 games with perfect completeness
On the Hardness of $4$-to-$1$ Games with Perfect Completeness
Computational Complexity
Summary
This paper shows that deciding between two extremes in a special kind of puzzle called a 4-to-1 game is very hard for computers—specifically, it is NP-hard. The authors confirm a long-standing theoretical conjecture from 2002 about these games. They also show that this hardness implies other difficult problems in graph coloring and hypergraph independent sets. The proof is done by building several layers of tests that carefully preserve the puzzle's perfect correctness when it has a solution.
What this means in practice
- •For graph algorithm designers: Recognize it is computationally infeasible to find small colorings for 3-colorable graphs due to hardness proven here.
- •For hypergraph software developers: Understand that finding large independent sets in 2-colorable 3-uniform hypergraphs cannot be efficiently approximated given this NP-hardness result.
A theory result. No direct application yet.
Authors
Yumou Fei, Dor Minzer, Shuo Wang
Abstract
We prove that for all $\varepsilon>0$, there exists a positive integer $k$ such that given a $4$-to-$1$ game $Ψ$ with alphabet size at most $k$, it is $\mathbf{NP}$-hard to distinguish between the case that $\mathrm{val}(Ψ)=1$ and the case that $\mathrm{val}(Ψ)\leq \varepsilon$. This confirms the $4$-to-$1$ Games Conjecture from [Khot, \textit{CCC 2002}]. Previously, the best known result, due to [Dinur, Khot, Kindler, Minzer, Safra], established the almost-perfect completeness version (but applied to the stricter problem of $2$-to-$1$ games). Using results from the literature, we get the following implications: (1) for all $k\in \mathbb{N}$, given a $3$-colorable graph $G$, it is $\mathbf{NP}$-hard to find a proper $k$-coloring; (2) for all $δ>0$, given a $2$-colorable $3$-uniform hypergraph $G$, it is $\mathbf{NP}$-hard to find in it an independent set containing at least $δ$ fraction of the vertices. Our proof is a three-step construction that builds on the two-step framework of [Dinur, Khot, Kindler, Minzer, Safra]. In the outer-PCP step, we use quadratic equations to gain perfect completeness. We then construct a new middle PCP that performs low-rank tests while preserving a key covering property. Finally, we construct a new inner PCP based on a tensor of the standard Grassmann encoding with its low-rank variant due to [Golowich, FOCS 2023].