## Posts Tagged ‘complexity theory’

### Is solving a problem harder than recognizing a solution?

August 25, 2013

Consider the following thirty-eight numbers:

14,175  15,055,  16,616,  17,495,  18,072,  19,390,  19,731,  22,161,  23,320,

23,717,  26,343,  28,725,  29,127,  32,257,  40,020,  41,867,  43,155,  46,298,

56,734,  57,176,  58,306,  61,848,  65,825,  66,042,  68,634,  69,189,  72,936,

74,287,  74,537,  81,942,  82,027,  82,623,  82,802,  82,988,  90,467,  97,042,

97,507, 99,564.

Those numbers sum to 2,000,000. Can you break them into two groups of 19 numbers, where each group of numbers sums to 1,000,000?

Not so easy, is it? There are over 17 billion ways to break those numbers into two groups.

Suppose I showed you a solution. You could easily and quickly check my solution to see if it is correct.

So it seems that solving a problem is harder than recognizing a solution (i.e., deciding that a solution is correct).

But is that true? Perhaps we are overlooking something. Perhaps, if a solution can be efficiently recognized then there also exists an efficient way of solving the problem.

Can we answer this:

For every problem that can be efficiently recognized
is there an efficient way of solving the problem?

Suppose one day someone proves that the answer to that question is “Yes”.

The consequences will be revolutionary. Everything that was previously considered hard (cannot be solved by a computer) will be easily solved. We will be able to quickly learn just about everything, and the great mysteries of the world will fall quickly, from cures to deadly diseases, to the nature of the universe.

For example, consider its impact on cancer treatment. Modern cancer practice is to design custom treatments for individuals. Ideally a treatment would be customized to an individual’s specific DNA structure. But the human DNA consists of about 3 billion bases and the computations required for a completely customized treatment are astronomical, far beyond today’s computers. But if it were shown that all hard problems can be solved in an efficient way, then we could solve that customization problem quickly. That is, we could write software to determine the best treatment based on the individual’s specific 3 billion bases.

It has been an awakening for me to realize that it will be software and computing power that will be the key to solving many of today’s medical problems, meteorological problems, physics problems, etc. These problems require computations that are currently outside the capabilities of today’s computers. But in the future there will be computers capable of performing the necessary computations. Then the problems will fall.

The problem that I described above – for every problem that can be efficiently recognized, is there an efficient way of solving the problem – is a very famous problem. It is called the P = NP problem. It is one of the deepest questions that human beings have ever asked.

Most of the above material came from these two books:

1. P,  NP, and the Search for the Impossible by Lance Fortnow
2. Quantum Computing Since Democritus by Scott Aaronson