A factor-two approximation for shortest common superstring 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

A factor-two approximation for shortest common superstring

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.4 out of 5 (910 votes)

>>> How to Play <<<

A factor-two approximation for shortest common superstring. Gives a deterministic polynomial-time algorithm constructing a common superstring of length at most twice the optimum for every finite family of explicitly represented strings. The running time is polynomial in the full encoded input length, including symbol labels.

>>> Level Select <<<

LEVEL 1 A Polynomial-Time 2-Approximation for Shortest Common Superstring

released 2026-09-24 | 2 theorems · 14 lemmas · 17 proofs · 9,263 words | PLAY LEVEL 1 » (pdf)

We give a deterministic algorithm that, for every finite family of explicitly represented ordinary strings, outputs a common superstring of length at most twice the optimum in time polynomial in the total encoded input size, including symbol labels. The guarantee applies to the algorithm constructed here, not the classical maximum-overlap Greedy procedure.

More Theoretical computer science Games!
Sampling and counting contingency tables with arbitrary margins	Uniform identity testing for noncommutative formulas	Uniform sparsest cut: hardness and semidefinite gaps	Unbounded bin-packing gaps and the modified integer round-up conjecture
The Courtade–Kumar and Hellinger conjectures	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

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