P, NP, NP Complete, NP Hard – OMG

OK, so you want to learn about this no matter the price you have to pay 🙂
Then have some patience and read through the text. It could take some time to understand but it will happen. Let’s say this field is a marriage between classic mathematics and theoritical computer science.

What is it and Why is it requried?
While trying to find solutions for problems using algorithms (steps) we often encounter problems that are seemingly very difficult to solve.
We often end up racking our brain for some time to try and find out a simple solution. Now what if a solution might not exist and we spend our valuable time in attempting it. Why not spend that time instead to come up with an approximate solution, for example. So classifying problems might help us to know in which class our problem falls and how to go about it

Optimization Problem Vs Decision Problem
Before starting with various complexity classes let us first figure out what is an optimzation problem. Optimization problems are those where we try to maximize or minimize some value, say finding the shortest path in a graph for example. Contrast to this, Decision problems are those which have only one of the two possible answers – “yes” or “no”.
Simple decision problem: Given 10 numbers is there any number greater than 25
Another example: Given a graph, is there a cycle?

Now, let’s see few more definitions

Polynomial time:
Given an input n, polynomial time would be any polynomial based on n, like n2 or n3 or even n1000 etc. However n! , 2n are all non polynomial time. We can say any algorithm that runs in polynomial time is a tractable, simple or solvable problem.

All decision problems which have a solution working in polynomial time fall in this class Simple example: Sum of n numbers O(n) or sorting O(nlogn) or O(n2)

These are actually superset of P. However unlike P they don’t have (as yet) solution in polynomial time. However if we give an instance of the input and say that for this input the decision problem returns “yes”, we can verify the same in polynomial time. Non Polynomial time solution and polynomial time verification. P is a subset because its solutions can also be verified in polynomial time and solution runs in polynomial time also.
Let’s explain with an example: If there are 100 houses and each house has to be painted in a different color compared to all their friend’s house, it is not an easy problem to solve. However, the verification is trivial. If I already paint them in different colors and ask you to check if the painting has been done as per the above constraints, it is rather easy to verify the same. Go one by one for each house, see its color, check that it does not match with the color of friend’s house. Done ! Polynomial time verification !!

Till now, we can quickly make out that P are ‘easy’ problems and NP or ‘not so easy’ problems since we do not have a solution that can work in reasonable time

One more definition before proceeding further

Polynomial time reduction:
We say that decision problem P reduces to decision problem Q in polynomial time if we can make a function f(x) to convert all inputs of P to Q such that if f(x) is given to Q and we get “yes” we will get “yes” if we give x to P. Basically what we are doing is converting one problem to another. It might seem funny to computer science graduates. Imagine if I were to tell that to sort n numbers we can actually convert it into a problem of graph theory and solve it. But that is what Polynomial reduction is and it is significant here.

How about the problems which are in NP and are the hardest to solve among them. Such problems are called NP-Complete.
So, if we arrange in order the problems based on how easy it is solve, from easiest to hardest, it would be P — NP — NP Complete.
We can also call the NP-Complete problems as “Hard” problems that are in NP. Mathematically if all problems ‘x’ in NP can reduce in polynomial time to another problem ‘y’ in NP, we call the problem ‘y’ as NP complete
Please note: All NP-Complete problems have to reduce to each other because of the above definition. Example: “TSP: Is there a solution not exceeding cost k”

Now what is this. We already saw that ‘hard’ problems in NP are called NP-Complete. What about the problems that are not in NP or for that matter not even decision problems. So there is a class for them. If a problem is as hard as every other problem in NP (like NP-Complete problems) but need not be in NP (unlike NP Complete problems which have to be in NP), such problems are called NP-hard. Example: Every NP-Complete problem is also NP-hard. Optimization problem – “TSP: Find least cost” : This is optimization problem and hence not in NP
Decision Problem but not in NP: “Halting problem” – Given a program and its input, will the program halt? Even though it is a decision problem, it is not in NP because even the verification of its solution cannot be done in polynomial time

Please look at the figure below for a brief on what we have learned


  • You can see the ‘P’ problems as green dots as subset of NP. They are the easy ones with polynomial time solution available
  • The ‘NP’ can be seen as blue dots. They don’t have a known polynomial time solution but their solution is verifiable in polynomial time
  • The ‘NP-Complete’ happens to be red dots. They can reduce all NP problems to themselves and additionally they sit inside NP itself
  • The ‘NP-Hard’ are similar that they can reduce all NP-Complete (thereby NP) to themselves but they don’t have to be part of NP
  • Additional Information
    • Though everyone is sure that P is a subset of NP, they don’t know if P=NP or P != NP. That is a million dollar prize question in clay university of mathematics. Since you are now armed with this learning why not attempt to crack the question and become a millionaire 🙂

What do we teach our kids 

Today morning near BTM, there was this school bus full of children. It was behind me and near the A2B stop the signal turned red. I stopped but was almost hit from behind by this bus. Not only that, the driver started honking trying to push me to skip the signal. I didn’t budge and also took the pic of the bus

Funny thing is that the moto written in the bus “Life’s lessons start at Treamis”

My Tech BEAST – The Dell Inspiron 5548

Dell has been a faithful brand, serving us with 10+ Years between our two laptops. The first was a Inspiron 1525 with Core 2 Duo + 2 GB RAM (2009) and the next was a sexier Inspiron N4010 Core i3 + 4 GB RAM (2011). I am using the 1525 and was feeling it aging gracefully. My daughter and brother-in-law seem to have taken a liking to it and I was wondering if I should get a new laptop.

In comes Inspiron again

After being such a loyal Inspiron guy, no other laptop (other than the new Mac Book) could pull me towards it. Only the Mac will restrict me from all my extra curricular endeavors.

On the lookout for a laptop I wanted to get the best config. Let’s see where I am

Processor: Core i7Broadwell – 2.7 GHz (upto 3 GHz)

RAM: 16 GB DDR3 1600MHz

Display: Touch, Full HD, IPS, 15.6 inches

Graphics: AMD Radeon with 4 GB DDR3 Cache

Hard Disk: 1 TB, Hybrid (8 GB Cache)

Keyboard: Backlit

Rest: HD webcam, Bluetooth 4, Latest WiFi, USB 3.0 and stuff

Looking forward to meeting and having a long time relationship with this beast. The model was not available locally at all (no 16 GB version – only 8 GB possible). Dell had only one model 87000 upwards here. Thanks to my colleagues who travel to US this month, I am getting my hand on one of this. Two more have bought this laptop on my recommendation. Here is hoping that they get to use it to its full potential 🙂

Cost (bought in US): 56000

Trying out GoDaddy Hosting

Moved my site from freehostia to godaddy. The domain name changes surprisingly took just 30 mins. I backed up my site there, exported and imported into goDaddy all in under 5 minutes. The photos and some media are missing but there were missing even in the old host. I need to review the speed of goDaddy. I think it should do fine.

The Journey called Life

What is the most entertaining and enthralling part of a roller coaster ride. Well it is the ride itself. Not the destination (which is anyway the same place you started). Ask Columbus why he undertook four risky voyages where he could have died or what is somebody gave him an option of revealing the result of those voyages before he started. He would have laughed at you and said that what mattered were the voyages themselves, not anything before or after that. Same with mountaineers. After they reach a summit they start looking for the next peak to scale. They never feel satisfied with the current achievement.

See a tense cricket match, chasing with a required run rate of more than 10 (like CSKs). Once the match is won what you get is only relief and not the excitement or tense happiness when you journeyed to reach the target.Life is life that. People who have achieved their targets are boring people bragging about what they have done. Instead look at people who are always on a journey. They are intense, active and full of vigor. Arise, Awake and Stop not till your goal is reached and WHEN your goal is reached make a new goal and again Arise and Awake and Stop not till that is also reached and you continue so on and so forth.I have seen numerous people who are fed up with their fight, fight to achieve success in life, fight to finish their studies, fight to settle in life (whatever that means). But they need to realize that it is the fight that keeps them going, that gives a purpose in life and a goal. Once the fight is over, there is nothing else to do. They say I will be happy after I do this. After I settle down in life, I will be happy. But it is the journey that you take to achieve that matters. Once you settle down, don’t settle, become unsettled and start again.

When I hit the highways to go to Pondicherry from Bangalore I get super excited. Even after so many years of driving up and down, I still feel like a child when I start the engine of the car. But once I reach the destination, there is only a relief of having reached safely, no huge burst of happiness. We need to learn to keep our life’s journey like that. Always on, doing something new, learning something different, fighting for a cause,keeping ourselves updated, providing a surprise help to someone in need, whatever it takes but the journey should be on because as some great person has once said “Satisfaction is only in efforts and not in attainment. Hence efforts are success and efforts are victory”

So on and on, let us make new journeys and new destinations till our final destination beckons…

The Society

You must have heard people say this at least a hundred times. What will society say? People are talking very bad about you. People are questioning your behavior. How will I ever show my face now?

In bible there is a story. There was a prostitute and the people (society) felt that she should be stoned to death. So they gathered with stones in hand. The girl ran to Jesus for help. The only thing Jesus said was “Anyone who had not committed any sin can throw the first stone on her”. No one dared. The so called society is filled with hypocrites, barbarians, thieves and perverts who don’t have any rights to point fingers at you. In fact they speak about you to pull you down to their levels. It helps their ego to see a good soul being tarnished so that they can say – “Ha, (s)he too is like us”. Simple proof of things – People freely talk shit about others without realizing that they themselves are a pile load of shit.

You probably have heard of this donkey story. A man and his son had to travel with their donkey from one town to another. The donkey being old and tired, they all walked. On their way were four people gossiping about something. The moment they saw this travelling party, they commented “Why on earth would someone have a donkey and not ride on it. How foolish can that be”. So the man and his son decided that it makes sense to ride on the donkey but since it was old and tired only one of them will ride it and the other walk beside. Since the man was himself old he rode the donkey and the son walked by his side. However they came across another set of 4 people in a tea stall, again discussing some unrelated stuff. They saw the man riding the donkey and said with a stern face. “What a cruel man; He rides happily while his poor son has to walk”. So the man decided to put his son on the donkey and walk beside. In the next stop, a further four people hissed among themselves but loud enough for the travelers to hear. They said “The poor old man had to walk in this age, while his young and arrogant son is riding”. The man thought for a while and decided that they both ride. However they had gone only a few hundred meters when they met the fourth set of four people who said, “How can human beings be so cruel to animals. The poor donkey is both old and tired and these two goons are sitting on top of it” and they were right too. So the man decided to heed to their words too. He tied the donkey front and hind legs with a rope and between him and his son they carried it. They felt happy that they finally managed to shut up everybody. However when they came to flooding river and had to cross it on a bridge, the donkey too afraid, started shaking, stumbled out of their hands, fell into the river and died.

Moral of the Story (English) – When you start paying attention to what people gossip about you, you will end up with your ass in trouble

Moral of the Story (Hindi) – कुछ तो लोग कहेंगे, लोगों का काम हैं कहना छोडो, बेकार की बातो में , कही बीत ना जाए रैना

Moral of the Story (Tamil) – நாலு பேர் நாலு விதமாதான் பேசுவாங்க. அதபத்தி யோசிச்சா நம்ம நாள் தான் வீனா போகும்.

The Age of Internet Jealousy

Facebook (verb) is a nice fun activity. It helps to in one place get updates about our friends and family, what they are up to. It also allows us to provide a window for the world to see how we are doing, where we have been and what we have done of late. Whatever technology brings to the table, people will always remain the same. So if earlier we had to brag about the latest saree or gadjet in a family social meet, we do that now much faster and more often using facebook. We want the world to see and fume inside the great life that we are living. So it is not uncommon to find photos of us on a family trip to Dubai or flaunting the latest costly gift that our spouse gave us. Nothing wrong with that, basically we are updating that we have been on a trip. What could be wrong with that? The intention. That is what is wrong with it. The best category of photos and updates goes to personal relationships. A personal close photograph becomes a public object to kindle jealousy among the not-so-close people or worse still people who are yet to find a meaningful relationship. Worse yet are the updates like – see my husband cooks food for me. I see the updates frequency is the most and the content exotic among people living outside India. Funny still people who comment on them are also those who fall in the same category. Let us make some straightforward interpretations of these updates. They would be something like
“See what you are missing”
“I am so happy with my husband/wife”
“See where I am now. We were once so similar and in the same position”
“What a pathetic life you have got”
“Make your life meaningful. Go out and enjoy like me”
“See how beautiful my wife is”

One thing is, weak minded people do fall for this trap and begin feeling bad, exactly as what the (im)poster wanted to happen. So brace up. Our life is not a junk pile and we have much better things to do than make a feature film of our life. Still facebook is a nice entertainment for about 5-10 minutes a day.