|
aSYMMetrY, CO-Np, aND the WONDerS OF aLGOrIthMICa
the class of np is defined asymmetrically. It consists of all decision problems whose yes instances can be solved
in polynomial time with an ntm. notice, however, that we don’t say anything about the no instances. so, for
example, it’s quite clear that if there is a tour visiting each town in sweden exactly once, an ntm would answer
“yes” in a reasonable amount of time. If the answer is “no,” however, it may take its sweet time.
the intuition behind this asymmetry is quite accessible, really. the idea is that in order to answer “yes,” the ntm
need only (by “magic”) find a single set of choices leading to a computation of that answer. In order to answer
“no,” however, it needs to determine that no such computation exists. although this does seem very different, we
don’t really know if it is, though. You see, here we have another one of many “versus questions” in complexity
theory: np versus co-np.
the class co-np is the class of the complements of np problems. For every “yes” answer, we now want “no,”
and vice versa. If np is truly asymmetric, then these two classes are different, although there is overlap between
them. For example, all of p lies in their intersection, because both the yes and no instances in p can be solved in
polynomial time with an ntm (and by a deterministic turing machine, for that matter).
now consider what would happen if an np-complete problem Foo was found in the intersection of np and co-np.
First of all, all problems in np reduce to npC, so this would mean that all of np would be inside co-np (because
we could now deal with their complements, through Foo). Could there still be problems in co-np outside of np?
Consider such a hypothetical problem, bar. Its complement, co-bar, would be in np, right? but because np was
inside co-np, co-bar would also be in co-np. that means that its complement, bar, would be in np. but, but,
but … we assumed it to be outside of np—a contradiction!
In other words, if we find a single np-complete problem in the intersection of np and co-np, we’ll have shown
that np = co-np, and the asymmetry has disappeared. as stated, all of p is in this intersection, so if p = np, we’ll
also have np = co-np. that means that in algorithmica, np is pleasantly symmetric.
note that this conclusion is often used to argue that problems that are in the intersection of np and co-np are
probably not np-complete, because it is (strongly) believed that np and co-np are different. For example, no one has
found a polynomial solution to the problem of factoring numbers, and this forms the basis of much of cryptography.
Yet the problem is in both np and co-np, so most computer scientists believe that it’s not np-complete.
Chapter 11
■
hard problems and (lImIted) sloppIness
235
But Where Do You Start? And Where Do You Go from There?
I hope the basic ideas are pretty clear now: The class NP consists of all decision problems whose “yes” answers can be
verified in polynomial time. The class NPC consists of the hardest problems in NP; all problems in NP can be reduced
to these in polynomial time. P is the set of problems in NP that we can solve in polynomial time. Because of the
way the classes are defined, if there’s the least bit of overlap between P and NPC, we have P = NP = NPC. We’ve also
established that if we have a polynomial-time reduction from an NP-complete problem to some other problem in NP,
that second problem must also be NP-complete. (Naturally, all NP-complete problems can be reduced to each other
in polynomial time; see Exercise 11-2.)
This has given us what seems to be a useful notion of hardness—but so far we haven’t even established that there
exists such a thing as an NP-complete problem, let alone found one. How would we do that? Cook and Levin to the rescue!
In the early 1970s, Steven Cook proved that there is indeed such a problem, and a little later, Leonid Levin
independently proved the same thing. They both showed that a problem called boolean satisfiability, or SAT, is NP-
complete. This result has been named for them both and is now known as the Cook-Levin theorem. This theorem,
which gives us our starting point, is quite advanced, and I can’t give you a full proof here, but I’ll try to outline the
main idea. (A full proof is given by Garey and Johnson, for example; see the “References” section.)
The SAT problem takes a logical formula, such as (A or not B) and (B or C), and asks whether there is any
way of making it true (that is, of satisfying it). In this case, of course, there is. For example, we could set A = B = True.
To prove that this is NP-complete, consider an arbitrary problem FOO in NP and how you’d reduce it to SAT. The idea
is to first construct an NTM that will solve FOO in polynomial time. This is possible by definition (because FOO is in
NP). Then, for a given instance bar of FOO (that is, for a given input to the machine), you’d construct (in polynomial
time) a logical formula (of polynomial size) expressing the following:
The input to the machine was
•
bar.
The machine did its job correctly.
•
The machine halts and answers “yes.”
•
The tricky part is how you’d express this using Boolean algebra, but once you do, it seems clear that the NTM is,
in fact, simulated by the SAT problem given by this logical formula. If the formula is satisfiable—that is, if (and only if)
we can make it true by assigning truth values to the various variables (representing, among other things, the magical
choices made by the machine), then the answer to the original problem should be “yes.”
To recap, the Cook-Levin theorem says that SAT is NP-complete, and the proof basically gives you a way of
simulating NTMs with SAT problems. This holds for the basic SAT problem and its close relative, Circuit-SAT, where
we use a logical (digital) circuit, rather than a logical formula.
One important idea here is that all logical formulas can be written in what’s called conjunctive normal form
(CNF), that is, as a conjunction (a sequence of ands) of clauses, where each clause is a sequence of ors.
Each occurrence of a variable can be either of the form A or its negation, not A. The formulas may not be in CNF to
begin with, but they can be transformed automatically (and efficiently). Consider, for example, the formula A and (B
or (C and D)). It is entirely equivalent with this other formula, which is in CNF: A and (B or C) and (B or D).
Because any formula can be rewritten efficiently to a (not too large) CNF version, it should not come as a surprise
that CNF-SAT is NP-complete. What’s interesting is that even if we restrict the number of variables per clause to k and
get the so-called k-CNF-SAT (or simply k-SAT) problem, we can still show NP-completeness as long as k > 2. You’ll see
that many NP-completeness proofs are based on the fact that 3-SAT is NP-complete.
Chapter 11
■
hard problems and (lImIted) sloppIness
236
Do'stlaringiz bilan baham: |
