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.

Tuesday, 12 October 2010


Emotional needs can't be rationalized.  They need to be acknowledged.  Acknowledging feelings is not equivalent to indulging them.  Indulging feelings isn't always (ever?) the right thing to do.  What action can be taken after acknowledging your feelings when they are painful ones and you want to heal?  Is acknowledgment sufficient?

Strangely, none of this changes my answer.  I am still wont to respond with the former, yes, yes, yes and YES, in spite of how wrong it is.

There are the things that we consciously believe, and then there are the lies we tell ourselves to live with ourselves.

Monday, 11 October 2010


Humans are curious creatures that build emotional attachments with calculable predictability.  If you spend enough time with something or someone, you get used to it/him/her so that the sudden removal of that thing/person from your life makes you feel uncomfortable.  Such discomfort when caused by a person is often referred to as loneliness.

Even though it seems negative, it isn't always.  With the same calculable predictability, it will be overcome.
There was an error in this gadget