Why Everyone Predicted P Is Not Equal to NP — And Why the Evidence Is Shockingly Weak

Why Many Computer Scientists Believe P ≠ NP

The lecture explains why many computer scientists believe P ≠ NP, while emphasizing that the reasons are much weaker than a mathematical proof.

Algorithms are easier to find than limits are to prove

Researchers have repeatedly discovered clever algorithms that outperform expectations, such as Karatsuba’s multiplication algorithm. By contrast, proving that no efficient algorithm exists for a particular problem has been far harder.

The Traveling Salesperson Problem (TSP) illustrates this asymmetry. Brilliant algorithmists, including George Dantzig, Richard Karp, and Jack Edmonds, solved many important problems but did not find a fast algorithm for TSP. This may suggest that someone would have found a fast solution by now if one existed. The lecturer cautions, however, that this is suggestive—not proof.

Intuitions and historical clues

In a declassified letter from the 1950s, John Nash conjectured that certain ciphers would be infeasible to break in practice. If that conjecture is true, it would imply P ≠ NP, though Nash described the idea in terms of cryptography rather than the later language of complexity theory.

There is also a strong intuitive sense that solving a problem can be harder than checking a proposed solution. For example, solving a difficult Sudoku from scratch seems harder than verifying that a completed grid is correct. This intuition supports P ≠ NP, but intuition alone cannot establish the claim.

The history of proving computational limitations offers little reassurance. Turing’s work on undecidability showed that some problems cannot be solved at all. Since then, fully satisfying proofs that particular tasks cannot be performed efficiently have been scarce.

The central caution

Neither the track record of unsuccessful algorithm searches nor everyday intuitions amount to strong mathematical evidence. P versus NP is a precise mathematical question, and if P ≠ NP is true, it must have a proof. The excerpt ends as the lecturer begins to emphasize how little compelling evidence we currently have.

People and sources mentioned

• Speaker: Professor Tim Roughgarden
• People discussed: Alan Turing, Karatsuba, George Dantzig, Richard Karp, Jack Edmonds, and John Nash