Joeldi wrote:Okay, I've spent today reading up on this, and I get P, I get NP, and I get P ?= NP, but I cannot find a good explanation of what NP-Complete is. From what I read, it sounds like there is only 1 NP-Complete problem, and every other NP problem is just that one problem stacked on top of itself and described with different metaphors each time. But nothing I've read actually says that, everything just keeps on saying that there are >3000 completely different NP-Complete problems. Please for the love of god help me. Preferably with pictures and with as few Xs and Ys as possible.
There are many (technically an infinite number of) NP-complete problems. However, what they share is the following: if there is an efficient solution for any of them, there is an efficient solution for all of them. Furthermore, there is no harder problem which is still in NP.
The way this is typically proven is via the notion of a reduction. This is essentially a transformation of one problem into another, and perhaps a transformation of the answer back. (Technical note: this transformation has to be "easy", i.e. polynomial, for this to show completeness results.) For decision problems, the only things you can do to the answer is leave it the same or negate it.
A reduction of a problem A to a problem B
takes the input of a problem in A, transforms it into an input to problem B, and then transforms the answer back. What this does is show that problem A is no harder than problem B, sometimes written A <= B.
If you can do a reduction the other way too, you get that B <= A. And if A <= B and B => A, then A and B are both in the same complexity class. If either one is NP-complete, both are.
As an example of a reduction, let's take factoring and reduce it to boolean satisfiability (SAT). In some sense this is strange because factoring is not known to be NP-complete, and and factoring < SAT ("factoring is easier than SAT") is probably strict (and so they are not in the same complexity class). But it shows the direction you have to do the reduction in, and gives a flavor of a reduction without having to explain much about the problems. We're also doing a functional variant, not a decision problem. Sue me.
Factoring is simple. Given a number n
which is the product of two smaller numbers a
, find a
. Satisfiability is also simple. Given a boolean formula like (a and b) or (not c and a)
, find a way to set the variables to true or false so that the overall formula is true (or determine that is impossible). In that example, it's easy; e.g. c = false, b = false, a = true
is one satisfying assignment out of many.
So how do we factor? Let's say our input number is 56. That is representable in 6 bits (111000). So we set up a 6-bit multiplication table:
- Code: Select all
a b c d e f
* g h i j k l
m n o p q r
s t u v w x
y z A B C D
E F G H I J
K L M N O P
+ Q R S T U V
0 0 0 0 0 1 1 1 0 0 0
(You could fill in a lot more immediately.)
How does this work? Just as you learned in 3rd grade or whatever: r = l * f
, and v = k * d
, and n + u + B + I + P + (carries) = 1
Except in binary, multiplication is easy: 0 * 0 = 0
, 0 * 1 = 1
, 1 * 0 = 0
, and 1 * 1 = 1
: which looks awfully familiar if you draw a truth table. So r = l * f
becomes r = l and f
. Dealing with the addition is a bit harder because you have to make sure to take carries into account properly, but it can still be done. (That's why your computer can add, after all!) Finally, if you want to be a real stickler, you have to get rid of the equal signs. For r = l and f
you can just replace r
everywhere. For something like r = 1
, you can just say r
; for r = 0
, you say not r
Anyway, point being, we can translate that multiplication table into a boolean formula. And even though it'd be pretty big, the size is quadratic in the size of the input, and quadratic is polynomial so we're good.
And we can feed that formula to a SAT solver. And when it comes back and says that a = b = c = g = h = j = k = l = false
and d = e = f = i = true
gives a satisfying assignment, it's easy to translate that back into 7 * 8
, which is the answer to our original question.