http://en.wikipedia.org/wiki/P_versus_NP_problem
The P versus NP problem is a major unsolved problem in computer science. Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.
There is a US$ 1,000,000 prize to be won:
It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$ 1,000,000 prize for the first correct solution.
Consequences of the resolution of the problem
If P = NP
1. Problems for cryptography:
Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution to an NP-complete problem such as 3-SAT would break most existing cryptosystems including public-key cryptography, a foundation for many modern security applications such as secure economic transactions over the Internet, and symmetric ciphers such as AES or 3DES, used for the encryption of communications data. These would need to be modified or replaced by information-theoretically secure solutions.
2. Positive breakthroughs for logistics and biology:
Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in protein structure prediction, are also NP-complete; if these problems were efficiently solvable it could spur considerable advances in biology.
3. Revolution in mathematics:
According to Stephen Cook,
...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems.
If P ≠ NP
A proof that showed that P ≠ NP would lack the practical computational benefits of a proof that P = NP, but would nevertheless represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.
In other words, If P ≠ NP, it means that there are many common problems whereby there is no universal algorithm for an exact solution and brute force or creativity is the only way to try and arrive at an approximate solution whether by humans, computers or nature with finite resources of space and time.
Why is the N versus NP problem relevant to philosophy?
In this paper by Scott Aaronson: http://arxiv.org/pdf/1108.1791v3.pdf
From the abstract:
One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory—the field that studies the resources (such as time, space, and randomness) needed to solve computational problems—leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume’s problem of induction, Goodman’s grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis.
From the conclusion:
The purpose of this essay was to illustrate how philosophy could be enriched by taking computational complexity theory into account, much as it was enriched almost a century ago by taking computability theory into account.
And from the criticisms of Complexity Theory:
(3) Complexity theory focuses on only a limited type of computer—the serial, deterministic Turing machine—and fails to incorporate the “messier” computational phenomena found in nature.
With so much at stake, resolution of the P verses NP problem and it’s relevance from a computational complexity perspective (with it’s strengths and weaknesses), is certainly a fertile realm for philosophical investigations.
And there is the chance of winning US$ 1,000,000 as well.
