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
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
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