Thursday, 14 October 2010

Description of the P=NP Problem

This problem has to do with whether a certain class of hard-to-solve problems, designated NP-Complete, can be reduced to fast-to-solve problems, designated P.   Both NP-Complete and P problems belong to NP, a set of problems for which any given solution can be verified quickly.

The time it takes to find a solution for a problem varies for reasons beside the fact that they are dealing with differently sized inputs.  The set of P problems are known to be solved within a time proportional to the size the input; this makes them ‘fast-to-solve’. On the other hand, NP-Complete are characterized by the fact that the fastest known solutions to them take time proportional to an exponential function. In solving them, we usually can’t be more clever than by checking every possible solution in sequence. Thus the time required to solve these problem increases very quickly as the size of the input grows.  It grows so quickly, in fact, that solving a problem with a moderately large input can take the billions of years, using any amount of computing power available today.

A property of NP-Complete problems is that all problems within the set can be transformed to all the other problems within the set, making the problems in NP-Complete essentially reworded versions of each other. Thus if we could find a way to solve one problem quickly (i.e. reduce it to a P problem), we can solve them all quickly (and show P=NP).

A reason for the belief that P ≠ NP is that after 30 years of research, no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems.


The purpose of the assignment was to explain the problem in general terms and explain its importance for the general public.

After receiving a poor grade on this, I followed up with the following email:


I know my explanation for the belief that P doesn't equal NP is terse and I know I could have elaborated more but I think that ultimately, it really is the only answer. To take one example, consider cryptography. Billions of dollars worth of assets are protected by encryption protocols that are in essence NP-Complete problems. Because P!=NP is not proven, inductive reasoning (i.e. no known solutions to NP-Complete problems exist) and intuition (it doesn't 'feel' like there will be solution) are the only reasons why so much trust is placed on those protocols. Further, NP-Complete problems are found across the entire spectrum of math and science. The fact that so many smart people from disparate fields of study (NP-Complete problems are found in physics, chemistry, biology, cryptography, mathematics, computer science) could not find one solution since the problem was formulated three decades ago is what ultimately lets a multi-national bank trust its assets to some encryption method." which he retorted that I should have included these points in the first place.

In my defense, there was a cap based on word count, and I made cuts where I felt appropriate.  I guess I was wrong.
There was an error in this gadget