Perfect completeness for 2-to-1 games

The explanation

Here is a small puzzle with two kinds of players. Two left players each set two on-off switches, so each has four possible answers. Three right players each set one switch. A rule links every left player to every right player. Right player 1 must copy the left player's first switch. Right player 2 must copy the second switch. Right player 3 must say whether the two switches match, when facing left player 1. When facing left player 2, it must say whether they differ.

Every rule here has the same shape. For each answer a right player can give, exactly two left answers lead to it. A puzzle built only from rules of this shape is called a 2-to-1 game. Its value is the largest share of rules that one choice of answers can keep.

This puzzle cannot be fully solved. Right player 3 would have to say both "match" and "differ" about the same two switches. Yet five of the six rules can be kept. Checking all 128 ways to answer confirms it. The value is 5/6, about 83 percent, and 24 of those ways reach it.

Subhash Khot introduced games like this in 2002. He was studying hardness of approximation: which problems stay hard even when a rough answer is enough. His 2-to-1 Games Conjecture is about telling two kinds of game apart. Some are fully solvable. Others have a tiny value, such as 1 percent. The conjecture says this task is NP-hard. That means a fast method for it would give fast methods for every problem in a large class called NP.

The words "fully solvable" carry the weight. This demand is called perfect completeness. A theorem of Khot, Dor Minzer and Muli Safra, published in 2023, settled a weaker version. In it, the good games only need a value close to 1. But nearly solvable is not solvable. Those constructions need not produce even one game that can be fully solved. In 2014, Per Austrin, Ryan O'Donnell, Li-Yang Tan and John Wright kept perfect completeness for 2-to-1 games. But their bad games could still have value just above 23/24, about 96 percent. The open issue was pushing that down while keeping both demands. In September 2026, Yumou Fei, Minzer and Shuo Wang reached perfect completeness for the looser 4-to-1 games.

The single obstacle is the usual way of widening a gap. The standard trick plays a game many times at once. That pushes down the value of a bad game. But it breaks the 2-to-1 shape. Play one rule twice, and each pair of right answers comes from 2 × 2 = 4 left pairs. Play it k times, and there are 2^k.

This paper proves the gap can be widened anywaySource 1. Pick any fixed fraction δ between 0 and 1. The paper gives a fast, step-by-step translation from 3-SAT into 2-to-1 games. 3-SAT is a standard logic puzzle: true-false conditions, each on three variables. Solvable puzzles become games of value exactly 1. Unsolvable ones become games of value at most δSource 1. Every rule keeps exactly two left answers for each right answerSource 2. Instead of plain repetition, the paper places independent copies of a starting game in a treeSource 3. Its questions come from combining answers across that tree. Dropping one yes-or-no output merges at most two answers, so the two-to-one shape survivesSource 4.

Back in the switch puzzle, the theorem says this. No fast method can separate fully solvable 2-to-1 games from games keeping at most 1 percent of rules. The same holds for any fixed target in place of 1 percent, unless every NP problem has a fast methodSource 5. The number of answers per player is fixed, but it depends on δ. The running time is a fixed power of the input size, but that power may also depend on δSource 6. The paper also turns a known conditional limit on coloring most edges of a graph into an unconditional oneSource 7. It recovers a known hardness result of Johan Håstad for a three-variable constraint called Not-TwoSource 8.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. A tool called Comparator matches that proof against a fixed reference statement. The coloring and Not-Two consequences are not in the Lean scope note. No specialist review of the paper has been published.

What it doesn't show. This does not give a fast algorithm for any problem. Its games are not shown to meet the extra Rich 2-to-1 condition.