|
IS 2-Sat Np-COMpLete? WhO KNOWS …
When working with complexity classes, you need to be aware of special cases. For example, variations of
the knapsack problem (or subset sum, which you’ll encounter in a bit) are used for encryption. the thing is,
many cases of the knapsack problem are quite easy to solve. In fact, if the knapsack capacity is bounded by a
polynomial (as a function of the item count), the problem is in p (see exercise 11-3). If one is not careful when
constructing the problem instances, the encryption can be quite easy to break.
We have a similar situation with k-sat. For k
³3, this problem is np-complete. For k =2, though, it can be solved
in polynomial time. or consider the longest path problem. It’s np-hard in general, but if you happen to know that
your graph is a daG, you can solve it in linear time. even the shortest path problem is, in fact, np-hard in the
general case. the solution here is to assume the absence of negative cycles.
If you’re not working with encryption, this phenomenon is good news. It means that even if you’ve encountered a
problem whose general form is np-complete, it might be that the specific instances you need to deal with are in p.
this is an example of what you might call the instability of hardness. tweaking the requirements of your problem
slightly can make a huge difference, making an intractable problem tractable, or even an undecidable problem (such
as the halting problem) decidable. this is the reason why approximation algorithms (discussed later) are so useful.
does this mean that 2-sat is not np-complete? actually, no. drawing this conclusion is an easy trap to fall into.
this is true only if p
¹ np because otherwise all problems in p are np-complete. In other words, our
np-completeness proof fails for 2-sat, and we can show it’s in p, but we do not know that it’s not in npC.
Now we have a place to start: SAT and its close friends, Circuit SAT and 3-SAT. There are still lots of problems to
examine, though, and replicating the feat of Cook and Levin seems a bit daunting. How, for example, would you show
that every problem in NP could be solved by finding a tour through a set of towns?
This is where we (finally) get to start working with reductions. Let’s look at one of the rather simple NP-complete
problems, that of finding a Hamilton cycle. I already touched upon this problem in Chapter 5 (in the sidebar “Island-
Hopping in Kaliningrad”). The problem is to determine whether a graph with n nodes has a cycle of length n; that is,
can you visit each node exactly once and return to your starting point, following the edges of the graph?
This doesn’t immediately look as expressive as the SAT problem—there we had access to the full language
of propositional logic, after all—so encoding NTMs seems like a bit much. As you’ll see, it’s not. The Hamilton
cycle problem is every bit as expressive as the SAT problem. What I mean by this is that there is a polynomial-time
reduction from SAT to the Hamilton cycle problem. In other words, we can use the machinery of the Hamilton cycle
problem to create a SAT solving machine!
I’ll walk you through the details, but before I do, I’d like to ask you to keep the big picture in the back of your mind:
the general idea of what we’re doing is that we’re treating one problem as a sort of machine, and we’re almost
programming that machine to solve a different problem. The reduction, then, is the metaphorical programming. With that
in mind, let’s see how we can encode Boolean formulas as graphs so that a Hamilton cycle would represent satisfaction …
To keep things simple, let’s assume that the formula we want to satisfy is in CNF form. We can even assume 3-SAT
(although that’s not really necessary). That means we have a series of clauses we need to satisfy, and in each of these, we
need to satisfy at least one of the elements, which can be variables (such as A) or their negations (not A). Truth needs to
be represented by paths and cycles, so let’s say we encode the truth value of each variable as a direction of a path.
This idea is illustrated in Figure
11-3
. Each variable is represented by a single row of nodes, and these nodes are
chained together with antiparallel edges so that we can move from left to right or from right to left. One direction (say,
left to right) signifies that the variable is set to true, while the other direction means false. The number of nodes is
immaterial, as long as we have enough.
8
8
We need to stick with a polynomial number of nodes, of course.
Chapter 11
■
hard problems and (lImIted) sloppIness
237
Before we start trying to encode the actual formula, we want to force our machine to set each variable to exactly
one of the two possible logical values. That is, we want to make sure that any Hamilton cycle will pass through each
row (with the direction giving us the truth value). We also have to make sure the cycle is free to switch direction
when going from one row to the next, so the variables can be assigned independently of each other. We can do this
by connecting each row to the next with two edges, at the anchor points at either end (highlighted in Figure
11-3
), as
shown in Figure
11-4
.
Do'stlaringiz bilan baham: |
