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