\nWhile trying to find solutions for problems using algorithms (steps) we often encounter problems that are seemingly very difficult to solve.
\nWe 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.\u00a0Why not spend that time instead to come up with an approximate solution, for example.\u00a0So classifying problems might help us to know\u00a0in which class our problem falls and how to go about it<\/p>\n
Optimization Problem Vs Decision Problem<\/strong> Now, let’s see few more definitions<\/p>\n Polynomial time:<\/strong> CLASS\u00a0P<\/strong> CLASS NP<\/strong> 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<\/p>\n One more definition before proceeding further<\/p>\n Polynomial time reduction:<\/em> CLASS NP-COMPLETE<\/strong> Class NP-HARD<\/strong>
\nBefore starting with various complexity classes let us first figure out what is an optimzation problem.\u00a0Optimization problems are those where we try to maximize or minimize some value, say finding the shortest path in a graph for example.\u00a0Contrast to this, Decision problems are those which have only one of the two possible answers – “yes” or “no”.
\nSimple decision problem: Given 10 numbers is there any number greater than 25
\nAnother example: Given a graph, is there a cycle?<\/p>\n
\nGiven an input n, polynomial time would be any polynomial based on n, like n2<\/sup> or n3<\/sup> or even n1000<\/sup> etc. However\u00a0n! , 2n<\/sup>\u00a0are all non polynomial time. We can say any algorithm that runs in polynomial time is a tractable, simple or solvable problem.<\/p>\n
\nAll decision problems which have a solution working in polynomial time fall in this class\u00a0Simple example: Sum of n numbers O(n) or sorting O(nlogn<\/sub>) or O(n2<\/sup>)<\/p>\n
\nThese are actually superset of P. However unlike P they don’t have (as yet) solution in polynomial time.\u00a0However 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.\u00a0Non 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.
\nLet’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.\u00a0However, 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 !!<\/p>\n
\nWe 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.<\/p>\n
\nHow about the problems which are in NP and are the hardest to solve among them. Such problems are called NP-Complete.
\nSo, 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.
\nWe can also call the NP-Complete problems as “Hard” problems that are in NP.\u00a0Mathematically 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
\nPlease note: All NP-Complete problems have to reduce to each other because of the above definition.\u00a0Example: “TSP: Is there a solution not exceeding cost k”<\/p>\n
\nNow what is this. We already saw that ‘hard’ problems in NP are called NP-Complete.\u00a0What about the problems that are not in NP or for that matter not even decision problems.\u00a0So 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.\u00a0Example: Every NP-Complete problem is also NP-hard.\u00a0Optimization problem – “TSP: Find least cost” : This is optimization problem and hence not in NP
\nDecision 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<\/p>\n
![\"np\"](\"https:\/\/simonkayar.com\/wp-content\/uploads\/2016\/04\/np.jpg\")
<\/a><\/p>\n