Puzzles
Find the shortest route between cities. A million dollars says you can't — efficiently
Given a list of cities and the distances between them, find the shortest possible route that visits every city exactly once and returns to the start. For a handful of cities it's easy. For thousands, checking every possible route would outlast the universe. Is there a fast way to always find the best one?
Reveal the answer
Nobody knows. No algorithm has ever been found that solves every case efficiently, but nobody has proven one is impossible either — it's a specific case of the P versus NP problem, one of seven Millennium Prize Problems with a $1 million reward for a solution either way.
— Clay Mathematics Institute, P vs NP Millennium Prize Problem — Problem statement, 2000