program编程辅导、讲解CS，Java程序语言、Java，c++设计编程辅导 讲解留学生Processing|讲解留学生Processing
- 首页 >> Matlab编程 [I]n his short and broken treatise he provides an eternal example—not of laws, or
even of method, for there is no method except to be very intelligent, but of
intelligence itself swiftly operating the analysis of sensation to the point of
principle and definition.
— T. S. Eliot on Aristotle, “The Perfect Critic”, The Sacred Wood (1921)
The nice thing about standards is that you have so many to choose from;
furthermore, if you do not like any of them, you can just wait for next year’s model.
— Andrew S. Tannenbaum, Computer Networks (1981)
It is a rare mind indeed that can render the hitherto non-existent blindingly obvious.
The cry “I could have thought of that” is a very popular and misleading one, for the
fact is that they didn’t, and a very significant and revealing fact it is too.
— Dirk Gently to Richard McDuff
in Douglas Adams’ Dirk Gently’s Holistic Detective Agency (1987)
If a problem has no solution, it may not be a problem, but a fact —
not to be solved, but to be coped with over time.
— Shimon Peres, as quoted by David Rumsfeld, Rumsfeld’s Rules (2001)
12
NP-Hardness
12.1 A Game You Can’t Win
Imagine that a salesman in a red suit, who looks suspiciously like Tom Waits,
presents you with a black steel box with n binary switches on the front and
a light bulb on top. The salesman tells you that the state of the light bulb is
controlled by a complex boolean circuit—a collection of A,
O,
and N
gates
connected by wires, with one input wire for each switch and a single output
wire for the bulb. He then asks you a simple question: Is it possible to set
the switches so that the light bulb turns on? If you can answer this question
correctly, he will give you one million one hundred billion dollars; if you answer
incorrectly, or if you die without answering, he will take your soul.
x
y x x
y x∧y x∨y ¬x
Figure 12.1. An AND gate, an OR gate, and a NOT gate.
379
12. NP-HARDNESS
Figure 12.2. A boolean circuit. Inputs enter from the left, and the output leaves to the right.
As far as you can tell, the Adversary hasn’t connected the switches to the
light bulb at all, so no matter how you set the switches, the light bulb will stay
o.
If you declare that it is possible to turn on the light, the Adversary will open
the box and reveal that there is no circuit at all. But if you declare that it is
not possible to turn on the light, before testing all 2n settings, the Adversary
will magically create a circuit inside the box that turns on the light if and only
if the switches are in one of the settings you haven’t tested, and then flip the
switches to that setting, turning on the light. (You can’t detect the Adversary’s
cheating, because you can’t see inside the box until the end.) The only way
to provably answer the Adversary’s question correctly is to try all 2n possible
settings. You quickly realize that this will take far longer than you expect to
live, so you gracefully decline the Adversary’s oer.
The Adversary smiles and says, in a growl like Heath Ledger’s Joker after
smoking a carton of Marlboros, “Ah, yes, of course, you have no reason to trust
me. But perhaps I can set your mind at ease.” He hands you a large roll of
parchment—which you hope was made from sheep skin—with a circuit diagram
drawn (or perhaps tattooed) on it. “Here are the complete plans for the circuit
inside the box. Feel free to poke around inside the box to make sure the plans
are correct. Or build your own circuit from these plans. Or write a computer
program to simulate the circuit. Whatever you like. If you discover that the
plans don’t match the actual circuit in the box, you win the hundred billion
bucks.” A few spot checks convince you that the plans have no obvious flaws;
subtle cheating appears to be impossible.
But you should still decline the Adversary’s “generous” oer.
The problem
that the Adversary is posing is called circuit satisfiability or CS:
Given
a boolean circuit, is there a set of inputs that makes the circuit output T,
or
conversely, whether the circuit always outputs F.
For any particular input
setting, we can calculate the output of the circuit in polynomial (actually, linear)
time using depth-first-search. But nobody knows how to solve CS
faster
than trying all 2n possible inputs to the circuit by brute force, which requires
exponential time. Admittedly, nobody has actually formally proved that we can’t
380
12.2. P versus NP
beat brute force—maybe, just maybe, there’s a clever algorithm that just hasn’t
been discovered yet—but nobody has actually formally proved that anti-gravity
unicorns don’t exist, either. For all practical purposes, it’s safe to assume that
there is no fast algorithm for CS.
You tell the salesman no. He smiles and says, “You’re smarter than you look,
kid,” and then flies away on his anti-gravity unicorn.
12.2 P versus NP
A minimal requirement for an algorithm to be considered “ecient”
is that its
running time is bounded by a polynomial function of the input size: O(nc
) for
some constant c, where n is the size of the input.
Researchers recognized
early on that not all problems can be solved this quickly, but had a hard time
figuring out exactly which ones could and which ones couldn’t. There are
several so-called NP-hard problems, which most people believe cannot be solved
in polynomial time, even though nobody can prove a super-polynomial lower
bound.
A decision problem is a problem whose output is a single boolean value: Y
or N.
Let me define three classes of decision problems:
• P is the set of decision problems that can be solved in polynomial time.
Intuitively, P is the set of problems that can be solved quickly.
• NP is the set of decision problems with the following property: If the answer
is Y,
then there is a proof of this fact that can be checked in polynomial
time. Intuitively, NP is the set of decision problems where we can verify a
Y
answer quickly if we have the solution in front of us.
• co-NP is essentially the opposite of NP. If the answer to a problem in co-NP
is N,
then there is a proof of this fact that can be checked in polynomial
time.
For example, the circuit satisfiability problem is in NP. If a given boolean circuit
is satisfiable, then any set of m input values that produces T
output is a
proof that the circuit is satisfiable; we can check the proof by evaluating the
circuit in polynomial time. It is widely believed that circuit satisfiability is not
in P or in co-NP, but nobody actually knows.
Every decision problem in P is also in NP. If a problem is in P, we can verify
Y
answers in polynomial time recomputing the answer from scratch! Similarly,
every problem in P is also in co-NP.
This notion of eciency
was independently formalized by Alan Cobham in ,
Jack
Edmonds in ,
and Michael Rabin in ,
although similar notions were considered more
than a decade earlier by Kurt Gödel, John Nash, and John von Neumann.
381
12. NP-HARDNESS
Perhaps the single most important unanswered question in theoretical
computer science—if not all of computer science—if not all of science—is
whether the complexity classes P and NP are actually dierent.
Intuitively,
it seems obvious to most people that P 6= NP; the homeworks and exams in
your algorithms and data structures classes have (I hope) convinced you that
problems can be incredibly hard to solve, even when the solutions are simple
in retrospect. It’s completely obvious; of course solving problems from scratch
is harder than verifying that a given solution is correct. We can reasonably
accept—and most algorithm designers do accept—the statement “P 6= NP” as a
law of nature, similar to other laws of nature like Maxwell’s equations, general
relativity, and the sun rising tomorrow morning that are strongly supported by
evidence, but have no mathematical proof.
But if we’re being mathematically rigorous, we have to admit that nobody
knows how to prove that that P 6= NP. In fact, there has been little or no real
progress toward a proof for decades.
The Clay Mathematics Institute lists
P-versus-NP as the first of its seven Millennium Prize Problems, oering
a
$,,
reward for its solution. And yes, in fact, several people have lost
their souls, or at least their sanity, attempting to solve this problem.
A more subtle but still open question is whether the complexity classes NP
and co-NP are dierent.
Even if we can verify every Y
answer quickly, there’s
no reason to believe we can also verify N
answers quickly. For example, as far
as we know, there is no short proof that a boolean circuit is not satisfiable. It is
generally believed that NP 6= co-NP, but again, nobody knows how to prove it.
P
coNP NP
Figure 12.3. What we think the world looks like.
12.3 NP-hard, NP-easy, and NP-complete
A problem ⇧ is NP-hard if a polynomial-time algorithm for ⇧ would imply a
polynomial-time algorithm for every problem in NP. In other words:
⇧ is NP-hard () If ⇧ can be solved in polynomial time, then P=NP
Perhaps the most significant progress has taken the form of barrier results, which imply that
entire avenues of attack are doomed to fail. In a very real sense, not only do we have no idea
how to prove P 6= NP, but we can actually prove that we have no idea how to prove P 6= NP!
382
12.3. NP-hard, NP-easy, and NP-complete
Intuitively, if we could solve one particular NP-hard problem quickly, then we
could quickly solve any problem whose solution is easy to understand, using
the solution to that one special problem as a subroutine. NP-hard problems are
at least as hard as every problem in NP.
Finally, a problem is NP-complete if it is both NP-hard and an element of
NP (or “NP-easy”). Informally, NP-complete problems are the hardest problems
in NP. A polynomial-time algorithm for even one NP-complete problem would
immediately imply a polynomial-time algorithm for every NP-complete problem.
Literally thousands of problems have been shown to be NP-complete, so a
polynomial-time algorithm for one (and therefore all) of them seems incredibly
unlikely.
Calling a problem NP-hard is like saying “If I own a dog, then it can speak
fluent English.” You probably don’t know whether or not I own a dog, but I bet
you’re pretty sure that I don’t own a talking dog. Nobody has a mathematical
proof that dogs can’t speak English—the fact that no one has ever heard a dog
speak English is evidence, as are the hundreds of examinations of dogs that
lacked the proper mouth shape and brainpower, but mere evidence is not a
mathematical proof. Nevertheless, no sane person would believe me if I said I
owned a dog that spoke fluent English.
So the statement “If I own a dog, then
it can speak fluent English” has a natural corollary: No one in their right mind
should believe that I own a dog! Similarly, if a problem is NP-hard, no one in
their right mind should believe it can be solved in polynomial time.
P
NP coNP
NP-hard
NP-complete
Figure 12.4. More of what we think the world looks like.
It is not immediately obvious that any problems are NP-hard. The following
remarkable theorem was first published by Stephen Cook in
and
independently by Leonid Levin in .
. . . The department chair shakes his head sadly and says, “Oh, come on, that just sounds
like barking. Let me ask a question. Who was the greatest complexity theorist of all time?” The
dog cocks his head, pauses for a few seconds, and then says “Karp!” After the chair chases them
out of his oce,
the dog turns to its owner and says, “Maybe I should have said Impagliazzo?” Levin
first reported his results at seminars in Moscow in ,
while still a PhD student. News
of Cook’s result did not reach the Soviet Union until at least ,
after Levin’s announcement of
his results had been published; in accordance with Stigler’s Law, this result is often called “Cook’s
Theorem”. Levin was denied his PhD at Moscow University for political reasons; he emigrated to
the US in
and earned a PhD at MIT a year later. Cook was denied tenure by the Berkeley
383
12. NP-HARDNESS
The Cook-Levin Theorem. Circuit satisfiability is NP-hard.
I won’t even sketch a proof here, because I’ve been (deliberately) vague
about the definitions.
™12.4 Formal Definitions (HC SVNT DRACONES)
Formally, the complexity classes P, NP, and co-NP are defined in terms of
languages and Turing machines. A language is a set of strings over some finite
alphabet ⌃; without loss of generality, we can assume that ⌃ = {0, 1}. A Turing
machine is a very restrictive type of computer—crudely, a finite-state machine
with an unbounded memory tape—whose precise definition is surprisingly
unimportant. P is the set of languages that can be decided in Polynomial time
by a deterministic single-tape Turing machine. Similarly, NP is the set of all
languages that can be decided in polynomial time by a nondeterministic Turing
machine; NP is an abbreviation for Nondeterministic Polynomial-time.
The requirement of polynomial time is suciently
crude that we do not
have to specify the precise form of Turing machine (number of tapes, number
of heads, number of tracks, size of the tape alphabet, and so on). In fact, any
algorithm that runs on a random-access machine
in T(n) time can be simulated
by a single-tape, single-track, single-head Turing machine that runs in O(T(n)
4)
time. This simulation result allows us to argue formally about computational
complexity in terms of standard high-level programming constructs like arrays
and loops and recursion, instead of describing everything directly in terms of
Turing machines.
Formally, a problem ⇧ is NP-hard if and only if, for every language ⇧0 2 NP,
there is a polynomial-time Turing reduction from ⇧0 to ⇧. A Turing reduction
means a reduction that can be executed on a Turing machine; that is, a Turing
machine M that can solve ⇧0 using another Turing machine M0 for ⇧ as
a black-box subroutine. Turing reductions are also called oracle reductions;
polynomial-time Turing reductions are also called Cook reductions.
mathematics department in ,
just one year before publishing his seminal paper; he (but not
Levin) later won the Turing award for his proof.
Interested readers find a proof in my lecture notes on nondeterministic Turing machines at
http://algorithms.wtf, or in Boaz Barak’s excellent Introduction to Theoretical Computer Science. Random-access
machines are a model of computation that more faithfully models physical
computers. A standard random-access machine has unbounded random-access memory, modeled
as an unbounded array M[0 ..1] where each address M[i] holds a single w-bit integer, for
some fixed integer w, and can read to or write from any memory addresses in constant time.
RAM algorithms are formally written in assembly-like language, using instructions like ADD i, j, k
(meaning “M[i] M[ j] + M[k]”), INDIR i, j (meaning “M[i] M[M[ j]]”), and IF0GOTO i, `
(meaning “if M[i] = 0, go to line `”), but the precise instruction set is surprisingly irrelevant. By
definition, each instruction executes in unit time. In practice, RAM algorithms can be faithfully
described using higher-level pseudocode, as long as we’re careful about arithmetic precision.
384
12.5. Reductions and SAT
Researchers in complexity theory prefer to define NP-hardness in terms of
polynomial-time many-one reductions, which are also called Karp reductions.
A many-one reduction from one language L0 ✓ ⌃⇤ to another language L ✓ ⌃⇤
is a function f : ⌃⇤ ! ⌃⇤ such that x 2 L0 if and only if f (x) 2 L. Then we can
define a language L to be NP-hard if and only if, for any language L0 2 NP, there
is a many-one reduction from L0 to L that can be computed in polynomial time.
Every Karp reduction “is” a Cook reduction, but not vice versa. Specifically,
any Karp reduction from one decision problem ⇧ to another decision ⇧0 is
equivalent to transforming the input to ⇧ into the input for ⇧0
, invoking an
oracle (that is, a subroutine) for ⇧0
, and then returning the answer verbatim.
However, as far as we know, not every Cook reduction can be simulated by a
Karp reduction.
Complexity theorists prefer Karp reductions primarily because NP is closed
under Karp reductions, but is not closed under Cook reductions (unless NP=coNP,
which is considered unlikely). There are natural problems that are ()
NP-hard with respect to Cook reductions, but ()
NP-hard with respect to Karp
reductions only if P=NP. One trivial example of such a problem is US:
Given
a boolean formula, is it always false? On the other hand, many-one reductions
apply only to decision problems (or more formally, to languages); formally, no
optimization or construction problem is Karp-NP-hard.
To make things even more confusing, both Cook and Karp originally defined
NP-hardness in terms of logarithmic-space reductions. Every logarithmic-space
reduction is a polynomial-time reduction, but (as far as we know) not vice
versa. It is an open question whether relaxing the set of allowed (Cook or
Karp) reductions from logarithmic-space to polynomial-time changes the set of
NP-hard problems.
Fortunately, none of these subtleties rear their ugly heads in practice—in
particular, every reduction described in this chapter can be formalized as a
logarithmic-space many-one reduction—so you can wake up now.
12.5 Reductions and SAT
To prove that any problem other than circuit satisfiability is NP-hard, we use a
reduction argument. Reducing problem A to another problem B means describing
an algorithm to solve problem A under the assumption that an algorithm for
problem B already exists. You’ve already been doing reduction for years, even
before starting this book, only you probably called them something else, like
subroutines or utility functions or modular programming or using a calculator.
To prove something is NP-hard, we describe a similar transformation between
problems, but not in the direction that most people expect.
385
12. NP-HARDNESS
You should tattoo the following rule of onto the back of your hand, right
next to your mom’s birthday and the actual rules of Monopoly.
To prove that problem A is NP-hard,
reduce a known NP-hard problem to A.
In other words, to prove that your problem is hard, you need to describe an
ecient
algorithm to solve a dierent
problem, which you already know is
hard, using an hypothetical ecient
algorithm for your problem as a black-box
subroutine. The essential logic is a proof by contradiction. The reduction
implies that if your problem were easy, then the other problem would be easy,
which it ain’t. Equivalently, since you know the other problem is hard, the
reduction implies that your problem must also be hard; your hypothetical
ecient
algorithm does not actually exist.
As a canonical example, consider the formula satisfiability problem, usually
just called S.
The input to S
is a boolean formula like
(a _ b _ c _ d¯) , ((b ^ ¯c) _ (a¯ ) d) _ (c 6= a ^ b)),
and the question is whether it is possible to assign boolean values to the variables
a, b,c,... so that the entire formula evaluates to T.
To prove that S
is NP-hard, we need to give a reduction from a known
NP-hard problem. The only problem we know is NP-hard so far is CS,
so let’s start there.
Let K be an arbitrary boolean circuit. We can transform (or more accurately,
transcribe) K into a boolean formula
as follows. First, label each interior wire
by a new variable yj, and label the output wire with a new variable z. The
formula
consists of a list of equations, one for each gate, separated by As,
followed by a final ^ z. Figure .
shows the resulting transcription for our
example circuit.
Now we claim that the original circuit K is satisfiable if and only if the
resulting formula
is satisfiable. Like every other “if and only if” statement, we
prove this claim in two steps:
If a player lands on an available property and declines (or is unable) to buy it, that property
is immediately auctioned o
to the highest bidder; the player who originally declined the property
may bid, and bids may be arbitrarily higher or lower than the list price. Players in Jail can still
buy and sell property, buy and sell houses and hotels, and collect rent. The game has
houses
and
hotels; once they’re gone, they’re gone. In particular, if all houses are already on the
board, you cannot downgrade a hotel to four houses; you must raze all the hotels in the group
to the ground. Players can sell or exchange undeveloped properties with each other, but cannot
sell property back to the bank; on the other hand, players can sell buildings to the bank (at half
price), but cannot sell or exchange buildings with each other. All penalties are paid directly to
the bank. A player landing on Free Parking does not win anything. A player landing on Go gets
exactly $,
no more. Railroads are not magic transporters. Finally, Je
always gets the boot.
No, not the T-Rex or the penguin—the boot, dammit.
386
12.5. Reductions and SAT
x1
x2
x3
x4
x5
y1
y2
y3
y4
y5
y6
z
( y1 = x1 ^ x4) ^ ( y2 = x4) ^ ( y3 = x3 ^ y2) ^ ( y4 = y1 _ x2) ^
( y5 = x2) ^ ( y6 = x5) ^ ( y7 = y3 _ y5) ^ (z = y4 ^ y7 ^ y6) ^ z
Figure 12.5. Transcribing a boolean circuit as a boolean formula.
) Given a set of inputs that satisfy the circuit K, we can derive a satisfying
assignment for the formula
by computing the output of every gate in K.
( Given a satisfying assignment for the formula ,
we can obtain a satisfying
input the circuit by simply ignoring the internal wire variables yi and the
output variable z.
The entire transformation from circuit to formula can be carried out in linear
time. Moreover, the size of the resulting formula is at most a constant factor
larger than any reasonable representation of the circuit.
Now suppose, for the sake of argument, there is an algorithm that can
determine in polynomial time whether a given boolean formula is satisfiable.
Then given any boolean circuit K, we can decide whether K is satisfiable by first
transforming K into a boolean formula
as described above, and then asking
our magical mystery S
algorithm whether
is satisfiable, as suggested by the
following cartoon. Each box represents an algorithm. The red box on the left is
the transformation subroutine. The box on the right is the hypothetical magic
S
algorithm. It must be magic, because it has a rainbow on it.
C⌅⌃⇥ ⌅SAT
SAT
K
Boolean
formula
transform
in O(n)
time
Φ
Boolean
circuit
Φ is
satisfiable
Φ is not
satisfiable
T⌃ ⇤
F⇧⌥⇤
K is
satisfiable
K is not
satisfiable
T⌃ ⇤
F⇧⌥⇤
If you prefer magic pseudocode to magic boxes:
Kay
Erickson, personal communication, .
For those of you reading black-and-white
printed copies: Yes, that round thing is a rainbow.
387
12. NP-HARDNESS
CS(K):
transcribe K into a boolean formula
return S()
hh????MAGIC????ii
Transcribing K into
requires only polynomial time (in fact, only linear time,
but whatever), so the entire CS
algorithm also runs in polynomial time.
TCS(n)
O(n) + TS(O(n))
We conclude that any polynomial-time algorithm for S
would give us a
polynomial-time algorithm for CS,
which in turn would imply P=NP.
So S
is NP-hard!
12.6 3SAT (from CIRCUITSAT)
A special case of S
that is particularly useful in proving NP-hardness results is
called CNF-S
or more often simply S.
A boolean formula is in conjunctive normal form (CNF) if it is a conjunction
()
of several clauses, each of which is the disjunction ()
of several literals,
each of which is either a variable or its negation. For example:
clause z }| {
(a _ b _ c _ d) ^ (b _ ¯c _ d¯) ^ (a¯ _ c _ d) ^ (a _ ¯
b)
A CNF
formula is a CNF formula with exactly three literals per clause; the
previous example is not a CNF
formula, since its first clause has four literals
and its last clause has only two. S
is the restriction of S
to CNF
formulas:
Given a CNF
formula, is there an assignment to the variables that makes the
formula evaluate to T?
We could prove that S
is NP-hard by a reduction from the more general
S
problem, but it’s actually easier to start over from scratch, by reducing
directly from CS.
Figure 12.6. A polynomial-time reduction from CIRCUITSAT to 3SAT.
Given an arbitrary boolean circuit K, we transform K into an equivalent
CNF
formula in several stages. Except for the very last stage, this reduction
388
12.6. 3SAT (from CIRCUITSAT)
was actually described by Grigorii Tseitin in ,
five years before Cook and
Levin reported their proofs of the Cook-Levin Theorem. (In the same
paper, Tseitin described the problem we now call CNF-S,
possibly for the first
time.) As we describe each stage, we will also prove that stage is correct.
• Make sure every
and
gate in K has exactly two inputs. If any gate has
k > 2 inputs, replace it with a binary tree of k
1 binary gates. Call the
resulting circuit K0
. The circuits K and K0 are logically equivalent circuits,
so every satisfying input for K is a satisfying input for K0 and vice versa.
• Transcribe K0 into a boolean formula 1
with one clause per gate, exactly as in
our previous reduction to S.
We already proved that every satisfying input
for K0 can be transformed into a satisfying assignment for 1
and vice versa.
• Replace each clause in 1
with a CNF formula. There are only three types of
clauses in 1,
one for each type of gate in K0
:
a = b ^ c 7!
(a _ ¯
b _ ¯c) ^ (a¯ _ b) ^ (a¯ _ c)
a = b _ c 7!
(a¯ _ b _ c) ^ (a _ ¯
b) ^ (a _ ¯c)
a = ¯
b 7!
(a _ b) ^ (a¯ _ ¯
b)
Call the resulting CNF formula 2.
Because 1
and 2
are logically equivalent
formulas, every satisfying assignment for 1
is also a satisfying assignment
for 2,
and vice versa.
• Replace each clause in 2
with a CNF
formula. Every clause in 2
has at most
three literals, but we need clauses with exactly three literals. To obtain a
CNF
formula, we expand each two-literal clause in 2
into two three-literal
clauses by introducing one new variable, and we expand the final one-literal
clause in 2
into four three-literal clauses by introducing two new variables.
a _ b 7!
(a _ b _ x) ^ (a _ b _ x¯)
z 7!
(z _ x _ y) ^ (z _ x¯ _ y) ^ (z _ x _ ¯y) ^ (z _ x¯ _ ¯y)
Call the resulting CNF
formula 3.
Every satisfying assignment for 2
can be
transformed into a satisfying assignment for 3
by assigning arbitrary values
to the new variables (x and y). Conversely, every satisfying assignment
for 3
can be transformed into a satisfying assignment for 2
by ignoring
the new variables.
For example, our example circuit is transformed into the following CNF
formula;
compare with Figure ..
389
12. NP-HARDNESS
( y1 _ x1 _ x4) ^ ( y1 _ x1 _ z1) ^ ( y1 _ x1 _ z1) ^ ( y1 _ x4 _ z2) ^ ( y1 _ x4 _ z2)
^ ( y2 _ x4 _ z3) ^ ( y2 _ x4 _ z3) ^ ( y2 _ x4 _ z4) ^ ( y2 _ x4 _ z4)
^ ( y3 _ x3 _ y2) ^ ( y3 _ x3 _ z5) ^ ( y3 _ x3 _ z5) ^ ( y3 _ y2 _ z6) ^ ( y3 _ y2 _ z6)
^ ( y4 _ y1 _ x2) ^ ( y4 _ x2 _ z7) ^ ( y4 _ x2 _ z7) ^ ( y4 _ y1 _ z8) ^ ( y4 _ y1 _ z8)
^ ( y5 _ x2 _ z9) ^ ( y5 _ x2 _ z9) ^ ( y5 _ x2 _ z10) ^ ( y5 _ x2 _ z10)
^ ( y6 _ x5 _ z11) ^ ( y6 _ x5 _ z11) ^ ( y6 _ x5 _ z12) ^ ( y6 _ x5 _ z12)
^ ( y7 _ y3 _ y5) ^ ( y7 _ y3 _ z13) ^ ( y7 _ y3 _ z13) ^ ( y7 _ y5 _ z14) ^ ( y7 _ y5 _ z14)
^ ( y8 _ y4 _ y7) ^ ( y8 _ y4 _ z15) ^ ( y8 _ y4 _ z15) ^ ( y8 _ y7 _ z16) ^ ( y8 _ y7 _ z16)
^ ( y9 _ y8 _ y6) ^ ( y9 _ y8 _ z17) ^ ( y9 _ y6 _ z18) ^ ( y9 _ y6 _ z18) ^ ( y9 _ y8 _ z17)
^ ( y9 _ z19 _ z20) ^ ( y9 _ z19 _ z20) ^ ( y9 _ z19 _ z20) ^ ( y9 _ z19 _ z20)
Yikes! At first glance, this formula might look a lot more complicated than the
original circuit, but in fact, it’s only larger by a constant factor. Specifically, the
simplified circuit K0 has at most twice as many wires as the original circuit K,
each binary gate in K0 is transformed into at most five clauses in 3.
Even if the
formula size were a large polynomial function (like n374) of the circuit size, we
would still have a valid reduction.
Our reduction transforms an arbitrary boolean circuit K into a CNF
formula
3
in polynomial time (in fact, in linear time). Moreover, any satisfying
input for the input circuit K can be transformed into a satisfying assignment
for 3,
and any satisfying assignment for 3
can be transformed into a satisfying
input for K. In other words, K is satisfiable if and only if 3
is satisfiable. Thus,
if S
can be solved in polynomial time, then CS
can be solved in
polynomial time, which implies that P = NP. We conclude that S
is NP-hard.
12.7 Maximum Independent Set (from 3SAT)
For the next few problems we consider, the input is a simple, unweighted,
undirected graph, and the problem asks for the size of the largest or smallest
subgraph satisfying some structural property.
Let G be an arbitrary graph. An independent set in G is a subset of the
vertices of G with no edges between them. The maximum independent set
problem, which I’ll abbreviate MIS,
asks for the size of the largest
independent set in a given graph. I will prove that MIS
is NP-hard using
a reduction from S,
as suggested by Figure ..
Given an arbitrary CNF
formula ,
we construct a graph G as follows.
Let k denote the number of clauses in .
The graph G contains exactly 3k
vertices, one for each literal in .
Two vertices in G are connected by an
edge if and only if either ()
they correspond to literals in the same clause, or
()
they correspond to a variable and its inverse. For example, the formula
(a _ b _ c) ^ (b _ ¯c _ d¯) ^ (a¯ _ c _ d) ^ (a _ ¯
b _ d¯) is transformed into the graph
shown in Figure ..
390
12.7. Maximum Independent Set (from 3SAT)
S⇥
M⇥↵I⌃⇤S⌅
G
CNF
Boolean
formula
Φ
graph
Φ is
satisfiable
Φ is not
satisfiable
T⌥⌦⌅
F⇥⇧⌅
G has an
independent
set of size k
T⌥⌦⌅
F⇥⇧⌅
transform
in O(n)
time
G has no
independent
set of size k
=?
k
number of clauses in Φ
size of largest
independent
set in G
Figure 12.7. A polynomial-time reduction from 3SAT to MAXINDSET.
‾ ‾
a
b
c
c
d
a
b
d
b‾
d
a‾
‾c
(a _ b _ c) ^ (b _ ¯c _ d¯) ^ (a¯ _ c _ d) ^ (a _ ¯
b _ d¯)
Figure 12.8. A graph derived from the satisfiable 3CNF formula with 4 clauses, and an independent
set of size 4.
Each independent set in G contains at most one vertex from each clause
triangle, because any two vertices in each triangle are connected. Thus, the
largest independent set in G has size at most k. I claim that G contains an
independent set of size exactly k if and only if the original formula
is satisfiable.
As usual for “if and only if” statements, the proof consists of two parts.
) Suppose
is satisfiable. Fix an arbitrary satisfying assignment. By definition,
each clause in
contains at least one T
literal. Thus, we can choose
a subset S of k vertices in G that contains exactly one vertex per clause
triangle, such that the corresponding k literals are all T.
Because each
triangle contains at most one vertex in S, no two vertices in S are connected
by a triangle edge. Because every literal corresponding to a v
even of method, for there is no method except to be very intelligent, but of
intelligence itself swiftly operating the analysis of sensation to the point of
principle and definition.
— T. S. Eliot on Aristotle, “The Perfect Critic”, The Sacred Wood (1921)
The nice thing about standards is that you have so many to choose from;
furthermore, if you do not like any of them, you can just wait for next year’s model.
— Andrew S. Tannenbaum, Computer Networks (1981)
It is a rare mind indeed that can render the hitherto non-existent blindingly obvious.
The cry “I could have thought of that” is a very popular and misleading one, for the
fact is that they didn’t, and a very significant and revealing fact it is too.
— Dirk Gently to Richard McDuff
in Douglas Adams’ Dirk Gently’s Holistic Detective Agency (1987)
If a problem has no solution, it may not be a problem, but a fact —
not to be solved, but to be coped with over time.
— Shimon Peres, as quoted by David Rumsfeld, Rumsfeld’s Rules (2001)
12
NP-Hardness
12.1 A Game You Can’t Win
Imagine that a salesman in a red suit, who looks suspiciously like Tom Waits,
presents you with a black steel box with n binary switches on the front and
a light bulb on top. The salesman tells you that the state of the light bulb is
controlled by a complex boolean circuit—a collection of A,
O,
and N
gates
connected by wires, with one input wire for each switch and a single output
wire for the bulb. He then asks you a simple question: Is it possible to set
the switches so that the light bulb turns on? If you can answer this question
correctly, he will give you one million one hundred billion dollars; if you answer
incorrectly, or if you die without answering, he will take your soul.
x
y x x
y x∧y x∨y ¬x
Figure 12.1. An AND gate, an OR gate, and a NOT gate.
379
12. NP-HARDNESS
Figure 12.2. A boolean circuit. Inputs enter from the left, and the output leaves to the right.
As far as you can tell, the Adversary hasn’t connected the switches to the
light bulb at all, so no matter how you set the switches, the light bulb will stay
o.
If you declare that it is possible to turn on the light, the Adversary will open
the box and reveal that there is no circuit at all. But if you declare that it is
not possible to turn on the light, before testing all 2n settings, the Adversary
will magically create a circuit inside the box that turns on the light if and only
if the switches are in one of the settings you haven’t tested, and then flip the
switches to that setting, turning on the light. (You can’t detect the Adversary’s
cheating, because you can’t see inside the box until the end.) The only way
to provably answer the Adversary’s question correctly is to try all 2n possible
settings. You quickly realize that this will take far longer than you expect to
live, so you gracefully decline the Adversary’s oer.
The Adversary smiles and says, in a growl like Heath Ledger’s Joker after
smoking a carton of Marlboros, “Ah, yes, of course, you have no reason to trust
me. But perhaps I can set your mind at ease.” He hands you a large roll of
parchment—which you hope was made from sheep skin—with a circuit diagram
drawn (or perhaps tattooed) on it. “Here are the complete plans for the circuit
inside the box. Feel free to poke around inside the box to make sure the plans
are correct. Or build your own circuit from these plans. Or write a computer
program to simulate the circuit. Whatever you like. If you discover that the
plans don’t match the actual circuit in the box, you win the hundred billion
bucks.” A few spot checks convince you that the plans have no obvious flaws;
subtle cheating appears to be impossible.
But you should still decline the Adversary’s “generous” oer.
The problem
that the Adversary is posing is called circuit satisfiability or CS:
Given
a boolean circuit, is there a set of inputs that makes the circuit output T,
or
conversely, whether the circuit always outputs F.
For any particular input
setting, we can calculate the output of the circuit in polynomial (actually, linear)
time using depth-first-search. But nobody knows how to solve CS
faster
than trying all 2n possible inputs to the circuit by brute force, which requires
exponential time. Admittedly, nobody has actually formally proved that we can’t
380
12.2. P versus NP
beat brute force—maybe, just maybe, there’s a clever algorithm that just hasn’t
been discovered yet—but nobody has actually formally proved that anti-gravity
unicorns don’t exist, either. For all practical purposes, it’s safe to assume that
there is no fast algorithm for CS.
You tell the salesman no. He smiles and says, “You’re smarter than you look,
kid,” and then flies away on his anti-gravity unicorn.
12.2 P versus NP
A minimal requirement for an algorithm to be considered “ecient”
is that its
running time is bounded by a polynomial function of the input size: O(nc
) for
some constant c, where n is the size of the input.
Researchers recognized
early on that not all problems can be solved this quickly, but had a hard time
figuring out exactly which ones could and which ones couldn’t. There are
several so-called NP-hard problems, which most people believe cannot be solved
in polynomial time, even though nobody can prove a super-polynomial lower
bound.
A decision problem is a problem whose output is a single boolean value: Y
or N.
Let me define three classes of decision problems:
• P is the set of decision problems that can be solved in polynomial time.
Intuitively, P is the set of problems that can be solved quickly.
• NP is the set of decision problems with the following property: If the answer
is Y,
then there is a proof of this fact that can be checked in polynomial
time. Intuitively, NP is the set of decision problems where we can verify a
Y
answer quickly if we have the solution in front of us.
• co-NP is essentially the opposite of NP. If the answer to a problem in co-NP
is N,
then there is a proof of this fact that can be checked in polynomial
time.
For example, the circuit satisfiability problem is in NP. If a given boolean circuit
is satisfiable, then any set of m input values that produces T
output is a
proof that the circuit is satisfiable; we can check the proof by evaluating the
circuit in polynomial time. It is widely believed that circuit satisfiability is not
in P or in co-NP, but nobody actually knows.
Every decision problem in P is also in NP. If a problem is in P, we can verify
Y
answers in polynomial time recomputing the answer from scratch! Similarly,
every problem in P is also in co-NP.
This notion of eciency
was independently formalized by Alan Cobham in ,
Jack
Edmonds in ,
and Michael Rabin in ,
although similar notions were considered more
than a decade earlier by Kurt Gödel, John Nash, and John von Neumann.
381
12. NP-HARDNESS
Perhaps the single most important unanswered question in theoretical
computer science—if not all of computer science—if not all of science—is
whether the complexity classes P and NP are actually dierent.
Intuitively,
it seems obvious to most people that P 6= NP; the homeworks and exams in
your algorithms and data structures classes have (I hope) convinced you that
problems can be incredibly hard to solve, even when the solutions are simple
in retrospect. It’s completely obvious; of course solving problems from scratch
is harder than verifying that a given solution is correct. We can reasonably
accept—and most algorithm designers do accept—the statement “P 6= NP” as a
law of nature, similar to other laws of nature like Maxwell’s equations, general
relativity, and the sun rising tomorrow morning that are strongly supported by
evidence, but have no mathematical proof.
But if we’re being mathematically rigorous, we have to admit that nobody
knows how to prove that that P 6= NP. In fact, there has been little or no real
progress toward a proof for decades.
The Clay Mathematics Institute lists
P-versus-NP as the first of its seven Millennium Prize Problems, oering
a
$,,
reward for its solution. And yes, in fact, several people have lost
their souls, or at least their sanity, attempting to solve this problem.
A more subtle but still open question is whether the complexity classes NP
and co-NP are dierent.
Even if we can verify every Y
answer quickly, there’s
no reason to believe we can also verify N
answers quickly. For example, as far
as we know, there is no short proof that a boolean circuit is not satisfiable. It is
generally believed that NP 6= co-NP, but again, nobody knows how to prove it.
P
coNP NP
Figure 12.3. What we think the world looks like.
12.3 NP-hard, NP-easy, and NP-complete
A problem ⇧ is NP-hard if a polynomial-time algorithm for ⇧ would imply a
polynomial-time algorithm for every problem in NP. In other words:
⇧ is NP-hard () If ⇧ can be solved in polynomial time, then P=NP
Perhaps the most significant progress has taken the form of barrier results, which imply that
entire avenues of attack are doomed to fail. In a very real sense, not only do we have no idea
how to prove P 6= NP, but we can actually prove that we have no idea how to prove P 6= NP!
382
12.3. NP-hard, NP-easy, and NP-complete
Intuitively, if we could solve one particular NP-hard problem quickly, then we
could quickly solve any problem whose solution is easy to understand, using
the solution to that one special problem as a subroutine. NP-hard problems are
at least as hard as every problem in NP.
Finally, a problem is NP-complete if it is both NP-hard and an element of
NP (or “NP-easy”). Informally, NP-complete problems are the hardest problems
in NP. A polynomial-time algorithm for even one NP-complete problem would
immediately imply a polynomial-time algorithm for every NP-complete problem.
Literally thousands of problems have been shown to be NP-complete, so a
polynomial-time algorithm for one (and therefore all) of them seems incredibly
unlikely.
Calling a problem NP-hard is like saying “If I own a dog, then it can speak
fluent English.” You probably don’t know whether or not I own a dog, but I bet
you’re pretty sure that I don’t own a talking dog. Nobody has a mathematical
proof that dogs can’t speak English—the fact that no one has ever heard a dog
speak English is evidence, as are the hundreds of examinations of dogs that
lacked the proper mouth shape and brainpower, but mere evidence is not a
mathematical proof. Nevertheless, no sane person would believe me if I said I
owned a dog that spoke fluent English.
So the statement “If I own a dog, then
it can speak fluent English” has a natural corollary: No one in their right mind
should believe that I own a dog! Similarly, if a problem is NP-hard, no one in
their right mind should believe it can be solved in polynomial time.
P
NP coNP
NP-hard
NP-complete
Figure 12.4. More of what we think the world looks like.
It is not immediately obvious that any problems are NP-hard. The following
remarkable theorem was first published by Stephen Cook in
and
independently by Leonid Levin in .
. . . The department chair shakes his head sadly and says, “Oh, come on, that just sounds
like barking. Let me ask a question. Who was the greatest complexity theorist of all time?” The
dog cocks his head, pauses for a few seconds, and then says “Karp!” After the chair chases them
out of his oce,
the dog turns to its owner and says, “Maybe I should have said Impagliazzo?” Levin
first reported his results at seminars in Moscow in ,
while still a PhD student. News
of Cook’s result did not reach the Soviet Union until at least ,
after Levin’s announcement of
his results had been published; in accordance with Stigler’s Law, this result is often called “Cook’s
Theorem”. Levin was denied his PhD at Moscow University for political reasons; he emigrated to
the US in
and earned a PhD at MIT a year later. Cook was denied tenure by the Berkeley
383
12. NP-HARDNESS
The Cook-Levin Theorem. Circuit satisfiability is NP-hard.
I won’t even sketch a proof here, because I’ve been (deliberately) vague
about the definitions.
™12.4 Formal Definitions (HC SVNT DRACONES)
Formally, the complexity classes P, NP, and co-NP are defined in terms of
languages and Turing machines. A language is a set of strings over some finite
alphabet ⌃; without loss of generality, we can assume that ⌃ = {0, 1}. A Turing
machine is a very restrictive type of computer—crudely, a finite-state machine
with an unbounded memory tape—whose precise definition is surprisingly
unimportant. P is the set of languages that can be decided in Polynomial time
by a deterministic single-tape Turing machine. Similarly, NP is the set of all
languages that can be decided in polynomial time by a nondeterministic Turing
machine; NP is an abbreviation for Nondeterministic Polynomial-time.
The requirement of polynomial time is suciently
crude that we do not
have to specify the precise form of Turing machine (number of tapes, number
of heads, number of tracks, size of the tape alphabet, and so on). In fact, any
algorithm that runs on a random-access machine
in T(n) time can be simulated
by a single-tape, single-track, single-head Turing machine that runs in O(T(n)
4)
time. This simulation result allows us to argue formally about computational
complexity in terms of standard high-level programming constructs like arrays
and loops and recursion, instead of describing everything directly in terms of
Turing machines.
Formally, a problem ⇧ is NP-hard if and only if, for every language ⇧0 2 NP,
there is a polynomial-time Turing reduction from ⇧0 to ⇧. A Turing reduction
means a reduction that can be executed on a Turing machine; that is, a Turing
machine M that can solve ⇧0 using another Turing machine M0 for ⇧ as
a black-box subroutine. Turing reductions are also called oracle reductions;
polynomial-time Turing reductions are also called Cook reductions.
mathematics department in ,
just one year before publishing his seminal paper; he (but not
Levin) later won the Turing award for his proof.
Interested readers find a proof in my lecture notes on nondeterministic Turing machines at
http://algorithms.wtf, or in Boaz Barak’s excellent Introduction to Theoretical Computer Science. Random-access
machines are a model of computation that more faithfully models physical
computers. A standard random-access machine has unbounded random-access memory, modeled
as an unbounded array M[0 ..1] where each address M[i] holds a single w-bit integer, for
some fixed integer w, and can read to or write from any memory addresses in constant time.
RAM algorithms are formally written in assembly-like language, using instructions like ADD i, j, k
(meaning “M[i] M[ j] + M[k]”), INDIR i, j (meaning “M[i] M[M[ j]]”), and IF0GOTO i, `
(meaning “if M[i] = 0, go to line `”), but the precise instruction set is surprisingly irrelevant. By
definition, each instruction executes in unit time. In practice, RAM algorithms can be faithfully
described using higher-level pseudocode, as long as we’re careful about arithmetic precision.
384
12.5. Reductions and SAT
Researchers in complexity theory prefer to define NP-hardness in terms of
polynomial-time many-one reductions, which are also called Karp reductions.
A many-one reduction from one language L0 ✓ ⌃⇤ to another language L ✓ ⌃⇤
is a function f : ⌃⇤ ! ⌃⇤ such that x 2 L0 if and only if f (x) 2 L. Then we can
define a language L to be NP-hard if and only if, for any language L0 2 NP, there
is a many-one reduction from L0 to L that can be computed in polynomial time.
Every Karp reduction “is” a Cook reduction, but not vice versa. Specifically,
any Karp reduction from one decision problem ⇧ to another decision ⇧0 is
equivalent to transforming the input to ⇧ into the input for ⇧0
, invoking an
oracle (that is, a subroutine) for ⇧0
, and then returning the answer verbatim.
However, as far as we know, not every Cook reduction can be simulated by a
Karp reduction.
Complexity theorists prefer Karp reductions primarily because NP is closed
under Karp reductions, but is not closed under Cook reductions (unless NP=coNP,
which is considered unlikely). There are natural problems that are ()
NP-hard with respect to Cook reductions, but ()
NP-hard with respect to Karp
reductions only if P=NP. One trivial example of such a problem is US:
Given
a boolean formula, is it always false? On the other hand, many-one reductions
apply only to decision problems (or more formally, to languages); formally, no
optimization or construction problem is Karp-NP-hard.
To make things even more confusing, both Cook and Karp originally defined
NP-hardness in terms of logarithmic-space reductions. Every logarithmic-space
reduction is a polynomial-time reduction, but (as far as we know) not vice
versa. It is an open question whether relaxing the set of allowed (Cook or
Karp) reductions from logarithmic-space to polynomial-time changes the set of
NP-hard problems.
Fortunately, none of these subtleties rear their ugly heads in practice—in
particular, every reduction described in this chapter can be formalized as a
logarithmic-space many-one reduction—so you can wake up now.
12.5 Reductions and SAT
To prove that any problem other than circuit satisfiability is NP-hard, we use a
reduction argument. Reducing problem A to another problem B means describing
an algorithm to solve problem A under the assumption that an algorithm for
problem B already exists. You’ve already been doing reduction for years, even
before starting this book, only you probably called them something else, like
subroutines or utility functions or modular programming or using a calculator.
To prove something is NP-hard, we describe a similar transformation between
problems, but not in the direction that most people expect.
385
12. NP-HARDNESS
You should tattoo the following rule of onto the back of your hand, right
next to your mom’s birthday and the actual rules of Monopoly.
To prove that problem A is NP-hard,
reduce a known NP-hard problem to A.
In other words, to prove that your problem is hard, you need to describe an
ecient
algorithm to solve a dierent
problem, which you already know is
hard, using an hypothetical ecient
algorithm for your problem as a black-box
subroutine. The essential logic is a proof by contradiction. The reduction
implies that if your problem were easy, then the other problem would be easy,
which it ain’t. Equivalently, since you know the other problem is hard, the
reduction implies that your problem must also be hard; your hypothetical
ecient
algorithm does not actually exist.
As a canonical example, consider the formula satisfiability problem, usually
just called S.
The input to S
is a boolean formula like
(a _ b _ c _ d¯) , ((b ^ ¯c) _ (a¯ ) d) _ (c 6= a ^ b)),
and the question is whether it is possible to assign boolean values to the variables
a, b,c,... so that the entire formula evaluates to T.
To prove that S
is NP-hard, we need to give a reduction from a known
NP-hard problem. The only problem we know is NP-hard so far is CS,
so let’s start there.
Let K be an arbitrary boolean circuit. We can transform (or more accurately,
transcribe) K into a boolean formula
as follows. First, label each interior wire
by a new variable yj, and label the output wire with a new variable z. The
formula
consists of a list of equations, one for each gate, separated by As,
followed by a final ^ z. Figure .
shows the resulting transcription for our
example circuit.
Now we claim that the original circuit K is satisfiable if and only if the
resulting formula
is satisfiable. Like every other “if and only if” statement, we
prove this claim in two steps:
If a player lands on an available property and declines (or is unable) to buy it, that property
is immediately auctioned o
to the highest bidder; the player who originally declined the property
may bid, and bids may be arbitrarily higher or lower than the list price. Players in Jail can still
buy and sell property, buy and sell houses and hotels, and collect rent. The game has
houses
and
hotels; once they’re gone, they’re gone. In particular, if all houses are already on the
board, you cannot downgrade a hotel to four houses; you must raze all the hotels in the group
to the ground. Players can sell or exchange undeveloped properties with each other, but cannot
sell property back to the bank; on the other hand, players can sell buildings to the bank (at half
price), but cannot sell or exchange buildings with each other. All penalties are paid directly to
the bank. A player landing on Free Parking does not win anything. A player landing on Go gets
exactly $,
no more. Railroads are not magic transporters. Finally, Je
always gets the boot.
No, not the T-Rex or the penguin—the boot, dammit.
386
12.5. Reductions and SAT
x1
x2
x3
x4
x5
y1
y2
y3
y4
y5
y6
z
( y1 = x1 ^ x4) ^ ( y2 = x4) ^ ( y3 = x3 ^ y2) ^ ( y4 = y1 _ x2) ^
( y5 = x2) ^ ( y6 = x5) ^ ( y7 = y3 _ y5) ^ (z = y4 ^ y7 ^ y6) ^ z
Figure 12.5. Transcribing a boolean circuit as a boolean formula.
) Given a set of inputs that satisfy the circuit K, we can derive a satisfying
assignment for the formula
by computing the output of every gate in K.
( Given a satisfying assignment for the formula ,
we can obtain a satisfying
input the circuit by simply ignoring the internal wire variables yi and the
output variable z.
The entire transformation from circuit to formula can be carried out in linear
time. Moreover, the size of the resulting formula is at most a constant factor
larger than any reasonable representation of the circuit.
Now suppose, for the sake of argument, there is an algorithm that can
determine in polynomial time whether a given boolean formula is satisfiable.
Then given any boolean circuit K, we can decide whether K is satisfiable by first
transforming K into a boolean formula
as described above, and then asking
our magical mystery S
algorithm whether
is satisfiable, as suggested by the
following cartoon. Each box represents an algorithm. The red box on the left is
the transformation subroutine. The box on the right is the hypothetical magic
S
algorithm. It must be magic, because it has a rainbow on it.
C⌅⌃⇥ ⌅SAT
SAT
K
Boolean
formula
transform
in O(n)
time
Φ
Boolean
circuit
Φ is
satisfiable
Φ is not
satisfiable
T⌃ ⇤
F⇧⌥⇤
K is
satisfiable
K is not
satisfiable
T⌃ ⇤
F⇧⌥⇤
If you prefer magic pseudocode to magic boxes:
Kay
Erickson, personal communication, .
For those of you reading black-and-white
printed copies: Yes, that round thing is a rainbow.
387
12. NP-HARDNESS
CS(K):
transcribe K into a boolean formula
return S()
hh????MAGIC????ii
Transcribing K into
requires only polynomial time (in fact, only linear time,
but whatever), so the entire CS
algorithm also runs in polynomial time.
TCS(n)
O(n) + TS(O(n))
We conclude that any polynomial-time algorithm for S
would give us a
polynomial-time algorithm for CS,
which in turn would imply P=NP.
So S
is NP-hard!
12.6 3SAT (from CIRCUITSAT)
A special case of S
that is particularly useful in proving NP-hardness results is
called CNF-S
or more often simply S.
A boolean formula is in conjunctive normal form (CNF) if it is a conjunction
()
of several clauses, each of which is the disjunction ()
of several literals,
each of which is either a variable or its negation. For example:
clause z }| {
(a _ b _ c _ d) ^ (b _ ¯c _ d¯) ^ (a¯ _ c _ d) ^ (a _ ¯
b)
A CNF
formula is a CNF formula with exactly three literals per clause; the
previous example is not a CNF
formula, since its first clause has four literals
and its last clause has only two. S
is the restriction of S
to CNF
formulas:
Given a CNF
formula, is there an assignment to the variables that makes the
formula evaluate to T?
We could prove that S
is NP-hard by a reduction from the more general
S
problem, but it’s actually easier to start over from scratch, by reducing
directly from CS.
Figure 12.6. A polynomial-time reduction from CIRCUITSAT to 3SAT.
Given an arbitrary boolean circuit K, we transform K into an equivalent
CNF
formula in several stages. Except for the very last stage, this reduction
388
12.6. 3SAT (from CIRCUITSAT)
was actually described by Grigorii Tseitin in ,
five years before Cook and
Levin reported their proofs of the Cook-Levin Theorem. (In the same
paper, Tseitin described the problem we now call CNF-S,
possibly for the first
time.) As we describe each stage, we will also prove that stage is correct.
• Make sure every
and
gate in K has exactly two inputs. If any gate has
k > 2 inputs, replace it with a binary tree of k
1 binary gates. Call the
resulting circuit K0
. The circuits K and K0 are logically equivalent circuits,
so every satisfying input for K is a satisfying input for K0 and vice versa.
• Transcribe K0 into a boolean formula 1
with one clause per gate, exactly as in
our previous reduction to S.
We already proved that every satisfying input
for K0 can be transformed into a satisfying assignment for 1
and vice versa.
• Replace each clause in 1
with a CNF formula. There are only three types of
clauses in 1,
one for each type of gate in K0
:
a = b ^ c 7!
(a _ ¯
b _ ¯c) ^ (a¯ _ b) ^ (a¯ _ c)
a = b _ c 7!
(a¯ _ b _ c) ^ (a _ ¯
b) ^ (a _ ¯c)
a = ¯
b 7!
(a _ b) ^ (a¯ _ ¯
b)
Call the resulting CNF formula 2.
Because 1
and 2
are logically equivalent
formulas, every satisfying assignment for 1
is also a satisfying assignment
for 2,
and vice versa.
• Replace each clause in 2
with a CNF
formula. Every clause in 2
has at most
three literals, but we need clauses with exactly three literals. To obtain a
CNF
formula, we expand each two-literal clause in 2
into two three-literal
clauses by introducing one new variable, and we expand the final one-literal
clause in 2
into four three-literal clauses by introducing two new variables.
a _ b 7!
(a _ b _ x) ^ (a _ b _ x¯)
z 7!
(z _ x _ y) ^ (z _ x¯ _ y) ^ (z _ x _ ¯y) ^ (z _ x¯ _ ¯y)
Call the resulting CNF
formula 3.
Every satisfying assignment for 2
can be
transformed into a satisfying assignment for 3
by assigning arbitrary values
to the new variables (x and y). Conversely, every satisfying assignment
for 3
can be transformed into a satisfying assignment for 2
by ignoring
the new variables.
For example, our example circuit is transformed into the following CNF
formula;
compare with Figure ..
389
12. NP-HARDNESS
( y1 _ x1 _ x4) ^ ( y1 _ x1 _ z1) ^ ( y1 _ x1 _ z1) ^ ( y1 _ x4 _ z2) ^ ( y1 _ x4 _ z2)
^ ( y2 _ x4 _ z3) ^ ( y2 _ x4 _ z3) ^ ( y2 _ x4 _ z4) ^ ( y2 _ x4 _ z4)
^ ( y3 _ x3 _ y2) ^ ( y3 _ x3 _ z5) ^ ( y3 _ x3 _ z5) ^ ( y3 _ y2 _ z6) ^ ( y3 _ y2 _ z6)
^ ( y4 _ y1 _ x2) ^ ( y4 _ x2 _ z7) ^ ( y4 _ x2 _ z7) ^ ( y4 _ y1 _ z8) ^ ( y4 _ y1 _ z8)
^ ( y5 _ x2 _ z9) ^ ( y5 _ x2 _ z9) ^ ( y5 _ x2 _ z10) ^ ( y5 _ x2 _ z10)
^ ( y6 _ x5 _ z11) ^ ( y6 _ x5 _ z11) ^ ( y6 _ x5 _ z12) ^ ( y6 _ x5 _ z12)
^ ( y7 _ y3 _ y5) ^ ( y7 _ y3 _ z13) ^ ( y7 _ y3 _ z13) ^ ( y7 _ y5 _ z14) ^ ( y7 _ y5 _ z14)
^ ( y8 _ y4 _ y7) ^ ( y8 _ y4 _ z15) ^ ( y8 _ y4 _ z15) ^ ( y8 _ y7 _ z16) ^ ( y8 _ y7 _ z16)
^ ( y9 _ y8 _ y6) ^ ( y9 _ y8 _ z17) ^ ( y9 _ y6 _ z18) ^ ( y9 _ y6 _ z18) ^ ( y9 _ y8 _ z17)
^ ( y9 _ z19 _ z20) ^ ( y9 _ z19 _ z20) ^ ( y9 _ z19 _ z20) ^ ( y9 _ z19 _ z20)
Yikes! At first glance, this formula might look a lot more complicated than the
original circuit, but in fact, it’s only larger by a constant factor. Specifically, the
simplified circuit K0 has at most twice as many wires as the original circuit K,
each binary gate in K0 is transformed into at most five clauses in 3.
Even if the
formula size were a large polynomial function (like n374) of the circuit size, we
would still have a valid reduction.
Our reduction transforms an arbitrary boolean circuit K into a CNF
formula
3
in polynomial time (in fact, in linear time). Moreover, any satisfying
input for the input circuit K can be transformed into a satisfying assignment
for 3,
and any satisfying assignment for 3
can be transformed into a satisfying
input for K. In other words, K is satisfiable if and only if 3
is satisfiable. Thus,
if S
can be solved in polynomial time, then CS
can be solved in
polynomial time, which implies that P = NP. We conclude that S
is NP-hard.
12.7 Maximum Independent Set (from 3SAT)
For the next few problems we consider, the input is a simple, unweighted,
undirected graph, and the problem asks for the size of the largest or smallest
subgraph satisfying some structural property.
Let G be an arbitrary graph. An independent set in G is a subset of the
vertices of G with no edges between them. The maximum independent set
problem, which I’ll abbreviate MIS,
asks for the size of the largest
independent set in a given graph. I will prove that MIS
is NP-hard using
a reduction from S,
as suggested by Figure ..
Given an arbitrary CNF
formula ,
we construct a graph G as follows.
Let k denote the number of clauses in .
The graph G contains exactly 3k
vertices, one for each literal in .
Two vertices in G are connected by an
edge if and only if either ()
they correspond to literals in the same clause, or
()
they correspond to a variable and its inverse. For example, the formula
(a _ b _ c) ^ (b _ ¯c _ d¯) ^ (a¯ _ c _ d) ^ (a _ ¯
b _ d¯) is transformed into the graph
shown in Figure ..
390
12.7. Maximum Independent Set (from 3SAT)
S⇥
M⇥↵I⌃⇤S⌅
G
CNF
Boolean
formula
Φ
graph
Φ is
satisfiable
Φ is not
satisfiable
T⌥⌦⌅
F⇥⇧⌅
G has an
independent
set of size k
T⌥⌦⌅
F⇥⇧⌅
transform
in O(n)
time
G has no
independent
set of size k
=?
k
number of clauses in Φ
size of largest
independent
set in G
Figure 12.7. A polynomial-time reduction from 3SAT to MAXINDSET.
‾ ‾
a
b
c
c
d
a
b
d
b‾
d
a‾
‾c
(a _ b _ c) ^ (b _ ¯c _ d¯) ^ (a¯ _ c _ d) ^ (a _ ¯
b _ d¯)
Figure 12.8. A graph derived from the satisfiable 3CNF formula with 4 clauses, and an independent
set of size 4.
Each independent set in G contains at most one vertex from each clause
triangle, because any two vertices in each triangle are connected. Thus, the
largest independent set in G has size at most k. I claim that G contains an
independent set of size exactly k if and only if the original formula
is satisfiable.
As usual for “if and only if” statements, the proof consists of two parts.
) Suppose
is satisfiable. Fix an arbitrary satisfying assignment. By definition,
each clause in
contains at least one T
literal. Thus, we can choose
a subset S of k vertices in G that contains exactly one vertex per clause
triangle, such that the corresponding k literals are all T.
Because each
triangle contains at most one vertex in S, no two vertices in S are connected
by a triangle edge. Because every literal corresponding to a v