in circuit complexity cannot be pushed
much further. And, in fact, we haven’t
seen any significantly new circuit lower
bounds in the past 20 years.
Proof Complexity. Consider the set
of Tautologies, the Boolean formulas ø
of variables over ANDs, ORs, and NOTs
such that every setting of the variables
to True and False makes ø true, for example the formula
(x AND y) OR (NOT x) OR (NOT y).
A literal is a variable or its negation,
such as x or NOT x. A formula, like the
one here, is in Disjunctive Normal Form
(DNF) if it is the OR of ANDs of one or
more literals.
If a formula ø is not a tautology, we
can give an easy proof of that fact by exhibiting an assignment of the variables
that makes ø false. But if ø were indeed a
tautology, we don’t expect short proofs.
If one could prove there are no short
proofs of tautology that would imply P
≠ NP.
Resolution is a standard approach to
proving tautologies of DNFs by finding
two clauses of the form (y1 AND x) and
(y2 AND NOT x) and adding the clause
(y1 AND y2). A formula is a tautology exactly when one can produce an empty
clause in this manner.
In 1985, Wolfgang Haken21 showed
that tautologies that encode the pigeonhole principle (n + 1 pigeons in n holes
means some hole has more than one
pigeon) do not have short resolution
proofs.
Since then complexity theorists have
shown similar weaknesses in a number
of other proof systems including cutting
planes, algebraic proof systems based
on polynomials, and restricted versions
of proofs using the Frege axioms, the
basic axioms one learns in an introductory logic course.
But to prove P ≠ NP we would need
to show that tautologies cannot have
short proofs in an arbitrary proof system. Even a breakthrough result showing tautologies don’t have short general
Frege proofs would not suffice in separating NP from P.
Dealing with hardness
So you have an NP-complete problem
you just have to solve. If, as we believe, P
≠ NP you won’t find a general algorithm
that will correctly and accurately solve
your problem all the time. But sometimes you need to solve the problem
anyway. All hope is not lost. Here, I describe some of the tools one can use on
NP-complete problems and how computational complexity theory studies
these approaches. Typically one needs
to combine several of these approaches
when tackling NP-complete problems
in the real world.
Brute Force. Computers have gotten
faster, much faster since NP
-completeness was first developed. Brute force
search through all possibilities is now
possible for some small problem instances. With some clever algorithms
we can even solve some moderate size
problems with ease.
The NP-complete traveling salesperson problem asks for the smallest
distance tour through a set of specified
cities. Using extensions of the cutting-plane method we can now solve, in
practice, traveling salespeople problems with more than 10,000 cities (see
Applegate3).
Consider the 3SAT problem, solving
Boolean formula satisfiability where
formulas are in the form of the AND of
several clauses where each clause is the
OR of three literal variables or negations of variables). 3SAT remains NP-
complete but the best algorithms can
in practice solve SAT problems on about
100 variables. We have similar results
for other variations of satisfiability and
many other NP-complete problems.
But for satisfiability on general formulae and on many other NP-complete
problems we do not know algorithms
better than essentially searching all the
possibilities. In addition, all these algorithms have exponential growth in their
running times, so even a small increase
in the problem size can kill what was an
efficient algorithm. Brute force alone
will not solve NP-complete problems no
matter how clever we are.
Parameterized Complexity. Consider
the Vertex Cover problem, find a set of
k “central people” such that for every
compatible pair of people, at least one
of them is central. For small k we can
determine whether a central set of people exists efficiently no matter the total
number n of people we are considering.
For the Clique problem even for small k
the problem can still be difficult.
Downey and Fellows11 developed a
theory of parameterized complexity that
gives a fine-grained analysis of the complexity of NP-complete problems based
on their parameter size.
Approximation. We cannot hope to
solve NP-complete optimization problems exactly but often we can get a good
approximate answer. Consider the traveling salesperson problem again with
distances between cities given as the
crow flies (Euclidean distance). This
problem remains NP-complete but Arora4 gives an efficient algorithm that gets
very close to the best possible route.
Consider the MAX-CUT problem
of dividing people into two groups to
maximize the number of incompatibles
between the groups. Goemans and Williamson17 use semi-definite programming to give a division of people only a
.878567 factor of the best possible.
Heuristics and Average-Case Complexity. The study of NP-completeness
focuses on how algorithms perform on
the worst possible inputs. However the
specific problems that arise in practice
may be much easier to solve. Many computer scientists employ various heuristics to solve NP-complete problems that
arise from the specific problems in their
fields.
While we create heuristics for many
of the NP-complete problems, Boolean
formula Satisfiability (SAT) receives
more attention than any other. Boolean
formulas, especially those in conjunctive normal form (CNF), the AND of ORs
of variables and their negations, have a
very simple description and yet are general enough to apply to a large number
of practical scenarios particularly in
software verification and artificial intelligence. Most natural NP-complete
problems have simple efficient reductions to the satisfiability of Boolean formulas. In competition these SAT solvers
can often settle satisfiability of formulas
of one million variables.a
Computational complexity theorists study heuristics by considering
average-case complexity—how well can
algorithms perform on average from instances generated by some specific distribution.
Leonid Levin28 developed a theory of
efficient algorithms over a specific distribution and formulated a distributional version of the P versus NP problem.
Some problems, like versions of the