Skip to content →

NP Complete? Hard? Easy!

P, NP, NP Hard and NP complete are certain set of classes that include certain problems. Before you understand any of them it’s important to know a few terms.

Some jargon :

  • Decision Problem : something which returns true or false, is int x < 10?
  • Solved vs Verifiable : as the name suggests, you can solve for the value of x, whereas verifiable means given an input you can verify if the problem will return true or false
  • Reducing a problem/Reducible : You can reduce a problem to another, means you can transform one problem into another, and the output remains the same
    “Problem A is said to be reducible to B, if there exists a way to solve B and we can use that to solve for A too”

    Say we know how to take squares, and add two numbers and subtract numbers and divide, but we still don’t know how to multiply two numbers, then we can reduce
    ab to what is mentioned above, since if we can solve for the RHS, we can use that algorithm to solve for ab.

 

 

  • We say that set of all decision problems in the world that can be solved in polynomial time are in P.
  • Again all decision problems belonging to NP are problems that are verifiable in polynomial time.
  • A problem X belongs to NP complete if it belongs to NP, and all other problems  in NP can be reduced to X.
    So you’re reducing problem A in NP to problem X in NP complete, and if we know how to solve for X, we can use that to solve for A.
    Using the definition of NP complete, if we have an efficient way to solve for X, we can use that to solve for all problems in NP. So we just went from verifying a problem to solving a problem in polynomial time.
    This means all problem in NP can be solved in Polynomial time, that P = NP, and so far PNP and I think there is a million dollar reward if someone can prove that.
  • NP-hard, well these are by far the hardest problems. They are by definition atleast as a hard as any problem in NP-complete. Not all problems in NP-complete belong to NP-hard. And we say if a problem in NP-complete is reducible to a problem in NP-hard, and if we know how to solve even one NP-hard problem, we can solve all the NP-complete problems, and hence all the NP problems.

 

Intuitively you can imagine a set of hierarchy over here. P -> NP -> NP-Complete -> NP-Hard.

 

And also these are not the only classifications of problems there are several other classes of problems such as PPAD (we know a solution exists, but it is difficult to find the solution) and many more.

 

I hope this was clear, but certainly there are some stackoverflow answers which provide a much more intuitive definition.

https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard

https://stackoverflow.com/questions/306249/how-were-the-first-np-complete-problems-shown-to-be-np-complete?rq=1

https://stackoverflow.com/questions/210829/what-is-an-np-complete-in-computer-science?rq=1

Also, watch this great video.

Published in Algorithms

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.