P = NP

This is a big question of the century. Clays Mathematics Institute offers USD1,000,000 to a person who solves this problem.

Basically, we don't know whether P = NP. I would say likely not, but quoting the great musical Fermat's Last Tango, ``often things we think are not true, turn out to be true...''

One beautiful example is the discovery of the Simplex Algorithm in Linear Programming. Essentially, Linear Programming was an NP problem until about 1979. The discovery of Simplex is important - Linear Programming is used in many optimisation problems. So, maybe there's a P-time algorithm for every problem in NP. We just don't know.

Menaka Lashitha Bandara 2005-04-18