P, NP, and NP-Complete explained
I didn't fully understand the whole P = NP business until recently. Here's
- Reduction: The process of showing that one problem is a "subset"
of a another. If problem A reduces to problem B, problem A is a subset
of problem B. Thus, if you solve the "larger" problem (B),
you have solved the smaller one as well (A). For example, suppose you
want to solve the problem "ax + b = 0". This problem is obviously
a subset of problems like "jx^2 + kx + m = 0", taking
j = 0,k = a, and m = b. If you can solve the "jx^2 + kx + m = 0"
problems (such as by using the quadratic formula), then you can solve
the "ax + b = 0" problems. You don't have to come up with
a special solution
The main idea is that the little problem is just a special case of the
big problem. So, if you can solve every case of the big problem,
you can solve every case of the little problem.
The other aspect is difficulty. If it is really hard to solve "ax
+ b = 0" problems (just assume it is), then it must be as hard
or harder to solve "jx^2 + kx + m = 0" problems. After all,
the "jx^2 + kx + m = 0" problems have to solve the "hard"
"ax + b = 0" problems, in addition to other ones. If a kid
can't solve "ax+b", he surely cannot solve "jx^2 + kx
+ m = 0".
- Polynomial/exponential time: Exponential time means, in essence,
trying every possibility (slow). Polynomial time means having
some clever algorithm to solve a problem, so you don't try every possibility
(fast). Even time on the order of n^100 is faster than exponential
time for large enough n. Mathematically, polynomial time is O(n^k),
for some k. Exponential time is O(k^n), for some k.
- P: A problem that can be solved quickly (in polynomial
- NP: A problem that can be checked/verified quickly (polynomial
time). If I give you an answer to the problem, you can tell me if it
is right in polynomial time.
- NP-hard: A problem such that every problem in NP reduces to
it (every NP problem is a subset of it). NP-hard problems are not in
NP, so it takes a long time to even check them! If I give you
an answer, it takes a long time for you to tell me it is right!
- NP-complete (NPC): A problem that is both NP-hard and in NP.
This means that we can check an answer fast and every problem
in NP reduces to it. This means that solving any NPC problem
quickly will solve every NP problem quickly (therefore solving
the other NPC problems quickly as well).
Does P = NP? What's the fuss?
If P = NP, it means that every problem that can be checked quickly
can be solved quickly (remember the difference between checking
if an answer is right and actually solving a problem). This is a big deal,
because right now there are lots of NPC problems that can't be solved
quickly -- if P = NP, that means there is a way to solve them fast. This
is amazing, because some of these problems are really cool, really important,
and a fast way to solve them would be useful.
Remember that "quickly" means not trial-and-error. It could
take a billion years, but as long as you didn't use trial and error, it
was quick. Eventually a computer will come along that can turn that billion
years into a few minutes.
However, most people think that P does not equal NP. Why?
1) There are a lot of NPC problems, and after all these years, no one
has found a fast solution to any of them. This means that all those
researchers overlooked something.
2) There is a big difference between checking if an answer is right,
and finding the answer from scratch. If I give you a huge equation, and
tell you that 17 is a root, is it easier to check the root or find it
However, the problem is that no one has proven that P = NP, or that it
does not. That is, no one has shown that it is impossible to solve
an NPC problem in polynomial time. Nor have they given a way to solve
one in polynomial time.
So does P = NP? The official answer: It probably doesn't, but we can't
say for sure.