What exactly does it mean when a problem is NP complete?
In: Mathematics
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.
Latest Answers