Posts Tagged ‘problems’

What happened to the future? Why can’t we solve big problems anymore?

May 25, 2014

You promised me Mars colonies. Instead I got Facebook.

— Buzz Aldrin

It feels as if technologies have diverted us and enriched themselves with trivial toys, with things like iPhone and apps and social media and algorithms that speed automated trading. There’s nothing wrong with most of these things; they have expanded and enriched our lives. But they don’t solve humanities big problems. What happened to the future?

More …

There is discovery in solving every problem

September 2, 2013

A great discovery solves a great problem,
but there is a grain of discovery in the solution
of every problem. Your problem may be modest,
but if it challenges your curiosity and brings into
play your inventive facilities, and if you solve it
by your own means, you may experience the
tension and enjoy the triumph of discovery.

George Pólya, How To Solve It

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