The 2-to-1 Games Conjecture with perfect completeness at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

A
D
V
E
R
T

I
S
E
M
E
N
T

The 2-to-1 Games Conjecture with perfect completeness

at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

thinking... about 3 hours remaining

If this game doesn't work on your computer, go here for help. (Lean version available!)

expertly designed by an internal OpenAI model

Difficulty:	🧠🧠🧠🧠🧠	Ages:	13 - ∞
Skills:	algorithms, speed	Levels:	1
Category:	Theoretical computer science	Lean version:	YES! ✔
Rate this game! 4.2 out of 5 (8,389 votes)

>>> How to Play <<<

Perfect completeness for 2-to-1 games. Proves Khot's 2-to-1 Games Conjecture with perfect completeness: for every fixed rational $\delta\in(0,1)$, it is NP-hard to distinguish satisfiable games from games whose optimum is at most δ, on explicit unweighted instances. The alphabet depends only on δ, and every right-hand label has exactly two preimages under each constraint map.

>>> Level Select <<<

LEVEL 1 Perfect completeness for 2-to-1 games

released 2026-09-23 | 5 theorems · 22 lemmas · 31 proofs · 26,925 words | PLAY LEVEL 1 » (pdf)

We prove the 2-to-1 Games Conjecture with perfect completeness. For every fixed rational $\delta\in(0,1)$, it is NP-hard to distinguish satisfiable 2-to-1 games from games of value at most δ, with a fixed alphabet and an explicitly listed unweighted multiset of constraints.

More Theoretical computer science Games!
Almost-linear-time exact matching in general graphs	Almost-linear expected-time approximation of edit distance	Superpolynomial lower bounds and quasipolynomial reconstruction from deletion traces	Polynomial-time scheduling on three identical machines
The approximation threshold for metric $k$-median	Exponential semidefinite complexity of perfect matching	The asymptotic Gotsman–Linial conjecture	A factor-two approximation for shortest common superstring

COOLMAITH GAMES SPONSORS: (not real)
Big Al's USED GPUs	Epsilon & Delta LLP attorneys at limit	QED Bail Bonds	Hilbert's Hotel always a vacancy!

Cool Links: openai/math Lean Mathlib arXiv the real Coolmath Games

You are visitor number 000719

Thanks for visiting CoolmAIth Games
© 1997-2026 CoolmAIth Games. A parody. Not affiliated with Coolmath.com LLC or OpenAI.
Every proof here was written by an internal OpenAI model and lives at github.com/openai/math.
Best viewed in Netscape Navigator 4.0 at 800x600