What does it mean for a problem to be NP Hard or NP Complete?
In: Mathematics
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.
Latest Answers