Next: War Story: Hard Against Up: Intractable Problems and Approximations Previous: Other NP-Complete Problems

# The Art of Proving Hardness

Proving that problems are hard is a skill. But once you get the hang of it, reductions can be surprisingly straightforward and pleasurable to do. Indeed, the dirty little secret of NP-completeness proofs is that they are usually easier to create than explain, in the same way that it is often easier to rewrite old code than it is to understand and modify it.

I offer the following advice to those seeking to prove the hardness of a given problem:

• Make your source problem as simple (i.e. restricted) as possible.

Never try to use the general traveling salesman problem (TSP) as a source problem. Better, use Hamiltonian cycle, i.e. TSP where all the weights are 1 or . Even better, use Hamiltonian path instead of cycle, so you don't have to worry about closing up the path. Best of all, use Hamiltonian path on directed planar graphs where each vertex has total degree 3. All of these problems are equally hard, and the more you can restrict the problem that you are reducing, the less work your reduction has to do.

As another example, never try to use full satisfiability to prove hardness. Start with 3-satisfiability. In fact, you don't even have to use full 3-satisfiability. Instead, consider planar 3-satisfiability, where there is a way to draw the clauses as a graph in the plane such you can connect all instances of the same literal together without edges crossing. This property tends to be useful in proving the hardness of geometric problems. All these problems are equally hard, and hence NP-completeness reductions using any of them are equally convincing.

• Make your target problem as hard as possible.

Don't be afraid to add extra constraints or freedoms in order to make your problem more general. Perhaps your undirected graph problem can be generalized into a directed graph problem and can hence be easier to prove hard. Once you have a proof of hardness for the general problem, you can then go back and try to simplify the target.

• Select the right source problem for the right reason.

Selecting the right source problem makes a big difference in how difficult it is to prove a problem hard. Although theoretically any particular problem is as good as another, this is the first and easiest place to go wrong. When faced with trying to prove that a problem is hard, some people fish around through dozens of problems, looking for the one that seems the best fit. These people are amateurs; odds are they never will recognize what they are looking for when they see it.

I use four and only four problems as candidates for my hard source problem. Limiting them to four means that I can know a lot about each of these problems, such as which variants of these problems are hard and which are soft. My favorite problems are:

• 3-SAT: The old reliable. When none of the three problems below seem appropriate, I go back to the original source.
• Integer partition: This is the one and only choice for problems whose hardness seems to require using large numbers.
• Vertex cover: This is the answer for any graph problems whose hardness depends upon selection. Chromatic number, clique, and independent set all involve trying to select the correct subset of vertices or edges.
• Hamiltonian path: This is my choice for any graph problem whose hardness depends upon ordering. If you are trying to route or schedule something, Hamiltonian path is likely your lever into the problem.

• Amplify the penalties for making the undesired selection.

Many people are too timid in their thinking about hardness proofs. You are trying to translate one problem into another, while keeping the problems as close to their original identities as as possible. The easiest way to do this is to be bold with your penalties, to punish anyone for trying to deviate from your intended solution. Your thinking should be, ``if you select this element, then you have to pick up this huge set that prevents you from finding an optimal solution.'' The sharper the consequences for doing what is undesired, the easier it is to prove if and only if.

• Think strategically at a high level, then build gadgets to enforce tactics.

You should be asking yourself the following types of questions. ``How can I force that either A or B but not both are chosen?'' ``How can I force that A is taken before B?'' ``How can I clean up the things I did not select?'' After you have an idea of what you want your gadgets to do, you can worry about how to actually craft them.

• When you get stuck, alternate between looking for an algorithm or a reduction.

Sometimes the reason you cannot prove hardness is that there exists an efficient algorithm to solve your problem! Techniques such as dynamic programming or reducing to polynomial-time graph problems such as matching or network flow sometimes yield surprising polynomial algorithms. Whenever you can't prove hardness, it likely pays to alter your opinion occasionally to keep yourself honest.

Next: War Story: Hard Against Up: Intractable Problems and Approximations Previous: Other NP-Complete Problems

Algorithms
Mon Jun 2 23:33:50 EDT 1997