Thursday, December 2, 2010

What does the fact that P is not NP teach us?

The famous P versus NP problem in advanced mathematics has all of the ingredients of a great puzzle:

1) It is a problem which is relatively easy to explain to a layman.
2) The best minds in the world have been stumped by it.
3) There is an alleged one million dollar prize for its solution: http://claymath.org/millennium/P_vs_NP/
4) It has an elegant three page solution: http://arxiv.org/abs/cs.CC/0607093
5) The solution to the P versus NP problem has philosophical and religious implications.

The P versus NP problem is a problem about why certain problems in mathematics seem so difficult to solve, yet once a solution is known, it is very easy to verify that it is indeed a true solution. For instance, take the following set of integers, {-40, 67, 37, -7, 89, 34, 23, 32, 9}. Is there a subset of this set for which the sum of its elements adds up to 131? Try to solve it. You will find that it is not an easy problem to solve, even though it is an easy problem to state and it is easy to verify that the subset {67, 37, -7, 34} is indeed a solution. This problem is called the SUBSET-SUM problem. Mathematicians do not know of any efficient way of solving this type of problem on a computer.

The P versus NP problem can be stated as:

"Is the reason why solving the SUBSET-SUM problem seems so difficult because the SUBSET-SUM problem is inherently difficult or is there some clever method for solving this problem efficiently that mathematicians just have not found yet?"

The answer to this question is that the SUBSET-SUM problem seems so difficult to solve because it actually is inherently difficult to solve, i.e., in the language of modern mathematics, P is not equal NP. There are, in fact, no computers powerful enough to solve this problem when the number of elements in the set is larger than 100.

What does all of this mean? It means that there is a whole class of mathematics problems which we have virtually no chance of solving even with the help of modern computers - yet if G-d were to give us the solution, we could immediately verify that G-d's solution is indeed the correct solution.

There is a secular humanistic idea that we humans have the ability to figure everything out on our own, to create a perfect society where everyone is happy, living in peace and harmony without any type of religion guiding our lives. The solution to the P versus NP problem shows us that this idea is not grounded in reality. P not equal to NP tells us that we human beings were not created to solve complicated problems; even the computers that we build are only able to efficiently solve a limited class of problems.

We humans were only created to be able to understand the solutions to complicated problems, but not to solve the complicated problems. And this is why we are commanded to learn Torah, which has the answers to life's important questions, and why we were never expected try to figure these answers out on our own and succeed.

1 comment:

  1. The relationship of problem-solving power to the availability of time is interesting as a potential source of humility for human beings.

    ReplyDelete