What does it mean for a problem to be NP Hard or NP Complete?
In: Mathematics
Say you have a set of puzzles, such as jigsaws, rubix cubes, and brain teasers ( like metal pieces that have to sit together. Ones you are able to complete can go in the P category, and you have a method for completing them, which is your ‘algorithm’. Let’s say you finished a 100 piece jigsaw, which is now in P. You open a 5 million piece jigsaw; you know the algorithm to complete it, it may just take an indefinite amount of time. This is the NP complete class. NP Hard is when you can solve a problem with a harder algorithm, simplifying into an easier algorithm of another NP problem. This could be a brain teaser that might have some elements of a larger rubix cube, so it’s solvable algorithm might be reducable into a rubix cube algorithm.
The main basis for all of these is that a computer would have a very hard time solving certain problems ( travelling salesmen problem, etc.) They could hypothetically be solved, but a computer will have an polynomial running time that is not currently feasible. We put these problems into the P, NP and sub NP categories depending on their complexity.
First a quick eli5 style definition of “NP”: a class of problems which are very difficult to solve, but easy to verify a solution if offered, when simplified down to a Yes/No answer. The most well known example is the travelling salesman problem: given a list of cities and a complete cost table (eg: cost of a bus ride to/from every possible pair of cities), visit each city exactly once in sequence and come back to where you started for as little money as possible. Your job is to choose your visiting order. To make it a Yes/No problem, you are given a budget and asked if it’s even possible to accomplish within the budget. It’s actually really hard to verify for sure whether the answer is Yes or No, but if someone showed you a route, it would be really easy to verify that it is within the budget and that the answer is Yes.
So with that out of the way…
NP Hard problems are problems that, if for even 1 of them we could come up with a radical strategy that brings the difficulty down from “oh god it’s a nightmare” to “child’s play” (from the point of view of a computer), then ANY NP class problem could be brought down to “child’s play” difficulty. And to be clear, ALL NP class problems are currently nightmare difficulty.
An “NP Complete” problem means it is NP hard, but also in the NP category itself. There are categories more difficult than NP, and an NP-hard problem is allowed to be in these higher difficulty categories and still meet the above definition. An NP-Complete problem is also in the basic NP category. So that’s why they’re interesting.
All the known algorithms for solving NP Complete problems require exponential time to solve. Choosing the well-known travelling salesman problem, if there are *n* cities for the salesman to visit then the time taken to find the shortest trip will be, at best, proportional to *x^(n)*, where *x*>1. People have found ways of reducing *x* to very close to 1 but solving really large problems is not practical.
One of the biggest problems in computer science is to prove (or disprove) that NP Complete problems require exponential time.
Latest Answers