but these proofs are usually extremely long. But we can use the Occam razor principle to recognize and verify mathematical proofs as typically written in journals. We can then find proofs of theorems that have reasonable length proofs say in under 100 pages. A person who proves P = NP would walk home from the Clay Institute not with $1 million check but with seven (actually six since the Poincaré Conjecture appears solved).

Don’t get your hopes up. Complexity theorists generally believe P ≠ NP and such a beautiful world cannot exist.

 

approaches to Showing P ≠ NP

ILLUs TRATIon By C. E. B. REAs

Here, I present a number of ways we have tried and failed to prove P ≠ NP. The survey of Fortnow and Homer14 gives a fuller historical overview of these techniques.

Diagonalization. Can we just construct an NP language L specifically designed so that every single polynomial-time algorithm fails to compute L properly on some input? This approach,

known as diagonalization, goes back to the 19th century.

In 1874, Georg Cantor7 showed the real numbers are uncountable using a technique known as diagonalization. Given a countable list of reals, Cantor showed how to create a new real number not on that list.

Alan Turing, in his seminal paper on computation, 38 used a similar technique to show that the Halting problem is not computable. In the 1960s complexity theorists used diagonalization to show that given more time or memory one can solve more problems. Why not use diagonalization to separate NP from P?

Diagonalization requires simulation and we don’t know how a fixed NP machine can simulate an arbitrary P machine. Also a diagonalization proof would likely relativize, that is, work even if all machines involved have access to the same additional information. Baker, Gill and Solovay6 showed no relativ-izable proof can settle the P versus NP problem in either direction.

Complexity theorists have used di-

agonalization techniques to show some NP-complete problems like Boolean formula satisfiability cannot have algorithms that use both a small amount of time and memory, 39 but this is a long way from P ≠ NP.

Circuit Complexity. To show P ≠ NP it is sufficient to show some -complete problem cannot be solved by relatively small circuits of AND, OR, and NOT gates (the number of gates bounded by a fixed polynomial in the input size).

In 1984, Furst, Saxe, and Sipser15 showed that small circuits cannot solve the parity function if the circuits have a fixed number of layers of gates. In 1985, Razborov31 showed the NP-complete problem of finding a large clique does not have small circuits if one only allows AND and OR gates (no NOT gates). If one extends Razborov’s result to general circuits one will have proved P ≠ NP.

Razborov later showed his techniques would fail miserably if one allows NOT gates. 32 Razborov and Rudich33 develop a notion of “natural” proofs and give evidence that our limited techniques