YOUR teenage daughter wants to invite some friends to a party. She wants
Sally and Peter to come. And she would like Bob and Bill to be there. But she
doesn鈥檛 like Jill or Laura, and doesn鈥檛 want them to attend. Bob, however, likes
Jill, so he won鈥檛 come unless Jill is invited too. Peter can stomach either Jill
or Bob on their own, but hates the way they act when together, so he won鈥檛 come
if they are both invited. Sally will come if Bill doesn鈥檛, but not if Laura
does. And so the list goes on. Suppose there were thirty teenagers, all with
their own likes and dislikes. Could you help your daughter work out whom she
should invite?
You might want merely to work your way through all the possibilities, but
this could take years. As the number of teenagers increases, the tangled web of
constraints becomes horrendously complex. Even professional mathematicians would
struggle to find the answer. Mathematicians refer to this as the
鈥渟atisfiability鈥� problem. As far they know, there is no 鈥渆asy鈥� way to plan the
invitations.
While your daughter will only ruffle a few feathers if she gets it wrong,
variants of the problem also confront airlines with millions of flights to
schedule, and college administrators who must assign students, courses and
lecturers to available classrooms. Being able to solve this sort of problem
could be a lucrative business. For mathematicians, though, the interest is more
than commercial. The satisfiability problem relates to deeper questions, such
as: why are some mathematical problems easy and others hard? What is it that
makes a problem hard?
Advertisement
These are the kind of subtle questions that mathematicians generally approach
through careful definition of terms and abstract analysis. But now, as in
virtually every other branch of human endeavour, computers are weighing in. By
focusing the power of the silicon chip on the satisfiability problem,
mathematicians are painting a very complex and beautiful picture of the elusive
boundary between the easy and the hard.
In mathematical terms, a satisfiability problem is this: you have some
variables G, P and R, each of which can be either 鈥渢rue鈥� or 鈥渇alse鈥�. You also
have a logical expression involving these variables, something like: (G OR P)
AND (NOT G OR P) AND (NOT P OR NOT R). A clause such as (G OR P) is true if
either G or P (or both) is true. Otherwise it is false. And the entire
expression is true only if every clause is true. Now for the satisfiability
question: is there any way to assign true-false values to G, P and R that makes
the overall expression true?
True, true, false
In the party problem, the variables would correspond to your daughter鈥檚
friends (see Diagram). If G represents a potential guest named
Gabrielle, for example, then G being true means that Gabrielle is invited, while
G being false means she isn鈥檛. The expression above captures the relations
between Gabrielle and a pair of others, Peter and Robert. Your daughter likes
Gabrielle and Peter, and wants to invite them; hence the first clause (G OR P).
The second clause (NOT G OR P) means that since Peter is sensitive, you should
avoid inviting Gabrielle but not him (by either not inviting Gabrielle, or
inviting Peter, or both). And the third clause (NOT P OR NOT R) expresses your
daughter鈥檚 desire not to invite both Peter and Robert, as they hate each other.
To 鈥渟atisfy鈥� the expression, each of the clauses has to be true. After a bit of
scribbling, you can find the solution: G = true, P = true and R = false.
It isn鈥檛 so hard with just three variables. There are, after all, only eight
possible combinations to choose from. But with 20 variables there would be over
a million combinations. In a brute-force assault on such an expression, you
might have to try every possible combination before finding one that
works鈥攐r finding that nothing works. With this approach, the number of
computations needed to find a solution grows exponentially with the size of the
problem.
Easy way out
In a mathematician鈥檚 eyes, this rapid growth of computation time as the
problem size increases is the sign of a 鈥渉ard鈥� problem. But is there an easier
way of solving the problem? Is there, for example, an algorithm that could
decide whether an expression can be satisfied in a time that grows only
polynomially as the number of variables (N) increases? Where the time
increases as N7, say, rather than exponentially (7N)? This kind of
growth is much slower than exponential. If such an algorithm could be found, the
satisfiability problem would be no more difficult than adding up a list of
numbers. Unfortunately, despite many years of effort, mathematicians still can鈥檛
say whether or not any such algorithm exists.
Mathematicians refer to any problem that can be solved in polynomial time as
being in class P. These are the 鈥渆asy鈥� problems. Harder problems are known as
NP, which stands for 鈥渘ondeterministic polynomial鈥� time. A problem is in NP if
you can verify a proposed solution in a number of steps that grows polynomially
with the problem size. So if you happen to guess or stumble onto what you think
is a solution for a problem in NP, you can check it in polynomial time.
A jigsaw puzzle is a good example. Putting the pieces together is hard. But
once someone claims they have done it, you can easily check to see if they have
got it right. The more pieces there are, the longer it will take you to
check鈥攂ut the increase in time will be polynomial.
Any problem that is in P is clearly also in NP. But turn the question round
and it isn鈥檛 so easy鈥攁re there any NP problems that belong to P? Most
mathematicians believe that none do, but they can鈥檛 prove it. Just because you
can鈥檛 find a way of solving a problem in polynomial time doesn鈥檛 mean it can鈥檛
be done.
This lack of proof is a great annoyance, for it leaves in a muddle the
difference between what is easy and what is hard. Are the classes P and NP
distinct? Or could they be the same? Most computer scientists would be shocked
into a state of total disbelief if that turned out to be the case. Problems in
NP seem inherently more difficult than those in P, and demand a lot more work.
But we could be missing some magical perspective from which they would seem
easy鈥攏o one knows. This is probably the biggest unsolved problem in
theoretical computer science.
And the problem is even more complicated than it seems. For as difficult as
NP problems are, they are only the second step in a hierarchy of hard problems.
The next step up the ladder is the set of problems having the general form: 鈥淔or
all . . . does there exist . . . 鈥�? A military example might involve estimating
the resilience to attack of a network of roads connecting crucial cities. 鈥淔or
all ways an enemy might destroy half of these roads, would there still exist a
single route connecting all the cities?鈥� The hierarchy of difficulty goes on in
this way, topping out with the set of problems having the odd name 鈥減olynomial
蝉辫补肠别鈥�.
The question that plagues computer scientists is whether this hierarchy of
problems is real or illusory. If it鈥檚 real, then we can only hope to find
approximate solutions to hard problems. But if the classes somehow collapse onto
each other, then all the problems in the hierarchy can be quickly
solved鈥攊n polynomial time, that is.
One promising approach dreamt up by logicians involves a sort of speculative
game based on an 鈥渙racle鈥�, an imaginary all-knowing entity that could answer an
important question for us. Suppose, for example, the oracle could tell us
whether the satisfiability problem is in P or not. Then the game becomes one of
linking the satisfiability problem to other problems thought to be in NP. If we
can show that some of these problems can be reduced to the satisfiability
problem, then we鈥檇 have shown these problems were also in P. This approach ties
problems together in groups. All problems in a group fall into the same class of
difficulty, and a conclusion about one applies to all.
What mathematicians do know is that the satisfiability problem is what is
known as 鈥淣P-complete鈥�. That means that a very large number of problems in NP
can all be reduced to the SAT problem. So if SAT could be shown to be in P, then
NP would be a subset of P, and a lot of the problems we think are hard would
turn out to be easy. But without knowing which group the satisfiability problem
belongs to in the first place, the oracle approach doesn鈥檛 get us very far,
although it has produced useful insights.
Other mathematicians are taking a more practical approach, looking at the
satisfiability problem in great detail, and exploring how the easy and hard
problems are situated in problem space. The idea is to use a computer to
generate a few thousand random expressions and see how many can be satisfied,
and how much effort is required to find the solutions.
For technical reasons, it鈥檚 convenient to work with Boolean expressions in
what鈥檚 called 鈥渃onjunctive normal form鈥�. In this form, a clause is a set of
variables鈥攕uch as G, P and R in the earlier example鈥攋oined by the
operator OR, while a formula is a set of clauses linked by the operator AND. A
true formula is one that has no false clauses.
Most statistical studies are done with formulas composed of clauses of the
same length. Satisfiability problems with one or two variables in each clause
are uninteresting, as they can be solved in polynomial time. But problems with
three variables in each clause (3-SAT problems) are just as difficult as the
more general satisfiability problem. To generate a 3-SAT problem, three
variables are selected from the set of N variables, with an equal
probability that each will be negated or left in the affirmative. To build a
problem with M clauses, the process is repeated M times.
Let out clause
As it turns out, the ratio of clauses to variables, M/N, is
the critical parameter. When M/N is plotted against the
percentage of formulas that can be satisfied, the proportion of satisfiable
formulas decreases as M/N increases
(see Diagram).
Formulas with few clauses and many variables can almost always be
satisfied, since most of the variables occur only once or twice in the formula
and conflicts are rare. At the other end of the scale, with many clauses and few
variables, each variable can be expected to occur in many clauses, so conflicts
are frequent and the formulas are usually unsatisfiable.
What is surprising about the graph, though, is its specific shape. For small
formulas of, say, N = 10 variables, the transition from satisfiable to
unsatisfiable is gradual. But the transition becomes steeper as N
increases. At N = 50 the probability of satisfiability is close to 1
for ratios of M/N up to about 3. Then it falls steeply at all
ratios greater than about 4. It is this sharp 鈥減hase transition鈥� that cries out
for an explanation. This sudden transition also shows up鈥攁nd at the same
values of M/N鈥攊f we look at computational time instead
of the percentage of formulas that can be satisfied.
Scott Kirkpatrick of IBM鈥檚 Thomas J. Watson Research Center near New York,
working with mathematicians elsewhere, has recently shown that phase transitions
exist not only in the satisfiability problem but also in many other NP problems.
So it鈥檚 tempting to speculate that phase transitions are the defining
characteristic of the NP class: if a problem has a phase transition, then it
must be in NP. But some problems in P, such as 2-SAT, display phase transitions.
Conversely, there are problems in NP, like the travelling salesman problem (see
鈥淗ard Maths?鈥�, 28 October 1995, p 41), which don鈥檛 show such transitions.
Still, the phase transition perspective now seems to be one of the most
promising for finally finding the boundary between what is hard and what is
easy. Remarkably, scientists have also noticed that in its details, the phase
transition in the satisfiability problem corresponds almost exactly to what
physicists find in real physical substances undergoing phase
transitions鈥攊n a piece of iron, for example, which is non-magnetic when it
is hot, but spontaneously becomes magnetic when cooled. Why is there a
connection between NP problems and the behaviour of real substances? This is a
tantalising mystery.
So mathematicians are finally getting some idea, however vague, of the
mysterious no-man鈥檚-land between the hard and easy. Although the ratio of
M to N may not be a perfect indicator of how hard a problem is,
identifying its importance is a breakthrough. Your daughter could even use it to
see if she could get more than a handful of her friends to the party.