Posts Tagged ‘algorithms’

Computer Science Algorithms are way better than Mathematical Theorems

January 24, 2015

I see a great deal of beauty in mathematics. There is much beauty in a well-described, step-by-step proof of a theorem.

Lately I have been learning algorithms for parsing and compilers from a pair of marvelous books. [1] I think the author is one of the best technical writers in the world, which makes learning very enjoyable. As I learn the parsing and compiler algorithms described in the books, the same sense of beauty rises up inside me as with a good math theorem proof.

So both Mathematical theorems and Computer Science algorithms have tremendous beauty. Nonetheless, I think that Computer Science algorithms are way better than Mathematical theorems. Here’s why:

In Mathematics there is a tightly constrained framework in which one operates. There is a limited set of building blocks (axioms) and rules that one uses to perform work. Conversely, in Computer Science algorithms there is no such finite, well-defined set of building blocks and rules. Although there are commonly used techniques – recursion, closure, induction, etc. – there are an infinite number of concepts that may be used to create an algorithm. That infinite variety provides enormous power and complexity, and requires great creativity and ingenuity, and is why I think Computer Science algorithms are way better than Mathematical theorems.

[1] “Parsing Techniques” by Dick Grune et al, “Modern Compiler Design” by Dick Grune et al.

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