P, NP, and NP-Complete explained

I didn't fully understand the whole P = NP business until recently. Here's my explanation:

Intuitive Definitions

• 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 time).
  
• 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 yourself?

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.