Monthly Archives: April 2016

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 ūüôā