Hard problems and heuristic answers: solving a 12-airport TSP exactly at 62,741 km

A 12-airport traveling salesman problem was solved exactly at 62,741 km, while three heuristics chased that number with varying success. The OpenFlights dataset, with 3,425 nodes and 19,256 edges, reveals a heavy-tailed degree distribution where hubs are a minority but dominate connectivity. The post explores P vs NP, polynomial reductions, SAT, and Monte Carlo vs Las Vegas algorithms, illustrating the gap between provable and computable answers.