TSP Playground

— —

Pros
    Cons

      P vs NP — The $1,000,000 Question

      P = problems solvable in polynomial time (e.g. sorting). NP = problems whose solutions can be verified in polynomial time. Whether P = NP is one of the seven Millennium Prize Problems — unsolved since 1971, worth $1,000,000.

      Why TSP?

      TSP is NP-hard — at least as hard as any problem in NP. No polynomial-time exact algorithm is known. The fastest exact methods are still exponential or worse in the worst case. A polynomial-time TSP solver would immediately prove P = NP.

      What counts as a proof?

      Your solve(nodes) must: (1) always return the optimal (shortest possible) tour, and (2) run in polynomial time — O(nk) for some fixed k. Hit 📈 Test to measure both empirically across increasing sizes.

      solver.js Return an array of node indices (0-based) representing the tour.
      Visualization
      Complexity Test

      Runs your solve() at increasing sizes. Checks optimality against brute force for n ≤ 8, then estimates growth rate via log-log regression to determine if your algorithm is polynomial.

      n avg time runs optimality
      Proof Test

      Verifies your solve() finds the optimal tour on fixed test cases (seed 1337, n = 5–10). Optimality is confirmed by exhaustive brute force. All cases must pass for a valid P=NP proof candidate.

      n your dist optimal gap result