Computational problems, yet to be solved.

1363 articles with interactive demos, from what we already solve fast to what nobody has proved.

The difficulty map

From what we can solve fast to what nobody knows

Polynomial time

Solved and fast

Polynomial-time wins — exact and efficient

See all 753
SolvedDijkstra's AlgorithmThe greedy priority-queue trick that finds shortest paths in polynomial time — proven optimal since 1959.SolvedPageRankSolvedFast Fourier Transform

Browse by topic

Recently added

NP-hard

Hard but tamed

NP-hard, with strong heuristics and approximations

See all 177
NP-hardThe Traveling SalesmanShortest tour through every stop — the icon of NP-hardness, yet heuristics get within a few percent.NP-hardThe Knapsack ProblemNP-hardSudoku

Browse by topic

Recently added

Believed hard

Cryptography

Believed hard — and what quantum computers threaten

See all 128
Quantum-threatenedRSAMultiply two primes to lock it; factor them back to break it.Quantum-threatenedAESQuantum-threatenedDiffie-Hellman

Browse by topic

Recently added

Works, theory open

AI and learning

They work in practice; the theory is still open

See all 150
AI / heuristicBackpropagationHow neural networks learn: the chain rule run backward to tune every weight at once.AI / heuristicGradient DescentAI / heuristicTransformers & Attention

Browse by topic

Recently added

Undecidable

At the limits

Undecidable, intractable, or in a class of their own

See all 107
UndecidableThe Halting ProblemCan we tell if a program will ever stop? Turing proved no algorithm can — not slow, impossible.UndecidableConway's Game of LifeUndecidableGödel Incompleteness

Browse by topic

Recently added

Unsolved

The big question

Still unsolved

See all 48
UnsolvedP vs NPIf an answer is easy to check, is it always easy to find? The million-dollar question.$1M prizeThe Riemann HypothesisUnsolvedThe Collatz Conjecture

Browse by topic

Recently added