What exactly does it mean when a problem is NP complete?
In: Mathematics
Like a problem that doesn’t has a solution in satisfactory time with the actual computing power.
A problem is NP complete if:
1. It is solvable, even if the method to solving it is no more advanced than “Guess all the possible answers and see what fits”
2. It is easy/fast to check if the problem was solved without going trough the effort of solving it yourself.
3. You can transform the problem in to any other equivalent NP-complete problem.
What the other commenters are saying isn’t *strictly* correct, because they are assuming the solution to a famous unsolved computer science problem: that P is not equal to NP.
The set of P problems are any problems that can be solved quickly
The set of NP problems are problems whose solution can be verified quickly.
It is an open question if these two problems are the same: that if you can verify the solution to something quickly you can also find that solution quickly. While nearly all computer scientists believe that this is *not* the case no proof has been found.
A ‘problem’ is a question you can ask of a set of inputs. For example, “What is the sum of X and Y?” is a problem, and the numbers X and Y are the inputs. A particular instance of that problem is “What is the sum of 3 and 7?”, in which we instantiated it with the inputs 3 and 7.
P problems are problems for which the amount of steps it takes to solve them doesn’t grow too quickly as the input size grows. For addition, if you double the size of your inputs X and Y (e.g. from 3 and 7 to 35 and 72), the amount of steps it takes to add them up doubles. For multiplication, if you double the input sizes, it’ll take four times as long – you can check this by counting up the number of multiplications and additions you do in the pen-and-paper algorithm. In general, P problems have this form – if you double the input size, the amount of steps to solve the problem grows by some fixed multiplier. There are some problems which grow much faster, so we want problems to be in P (and preferably the lower echelons, where the number of steps isn’t being multiplied by anything much larger than 10-20 each time).
Note: P stands for polynomial, because if you write down the relationship between the input size and the number of steps, it can be written as a polynomial. The function x^2 has the relationship above – if we double x, x^2 becomes four times as large.
NP is interesting – it’s the set of problems where verifying a solution is in P. For example going back to the sum of X and Y, if we ask “Is 20 the sum of 3 and 7?”, we can very quickly say no, simply by doing the addition. Addition is therefore in NP – as is everything else in P. There are some problems, like “Can we use these roads to visit each city exactly once?”, which can be easily checked given a solution, but we don’t know whether or not they can be solved in P – our fastest solving algorithms are nearly just searching through every possiblity, which multiplies extremely quickly as the map grows.
Note: NP stands for nondeterministic polynomial, for reasons I won’t go into.
A reduction is a way to solve a problem using the machinery for another problem. For example, if I have a computer that solves “What is the sum of the list of numbers L?”, I could use this to solve the previous problem in two steps – put X and Y into L, and then put that into the list summer.
A problem is “complete” when all the problems in its category can be reduced to it with only a small (i.e. within the bounds of P) amount of steps. So, an NP-complete problem solver could be used as a module in a computer that solves every other NP problem quickly. This is an interesting thing for two reasons. First a theoretical one – these are the hardest problems in a class of problems, so they’re an easy way to bound the difficulty of the entire class. And on a practical one, if we found a fast way to solve even a single NP-complete problem, we would suddenly have this enormous and powerful set of problems simply handed to us.
It means the problem is both NP and NP-Hard.
Here’s the breakdown:
There are P problems. These are decision problems (yes/no answer problems) where the solution can be found quickly.
There are NP problems, which are decision problems where a solution can be *verified* quickly. E.g. if I give you a Sudoku puzzle solution, you can quickly check if I’m right or not. P problems are also in NP because if you want to verify an answer to a P problem, you can just quickly find the solution yourself and compare them.
There are NP-Hard problems. Every problem in NP can be reduced to an NP-Hard problem. NP-Hard problems do not need to be decision problems and they do not need to be verified quickly. If you can solve an NP-Hard problem quickly, you can solve all NP problems quickly.
And then there are NP-Hard problems that are also in NP. These are called NP-Complete problems. These are kind of special because it means there are NP problems that can be reduced to other NP problems. And if you can solve any NP-Complete problem quickly, then you can solve all NP problems quickly.
Latest Answers