26
$\begingroup$

I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How should I approach a problem that asks me to prove a problem is NPC?

$\endgroup$
  • 4
    $\begingroup$ Sorry to disappoint, I don't think there is a method that solves-it-all. Like many problems in life, each is unique.. Hopefully, with time, you'll get the right hunch how to solve each. $\endgroup$ – Ran G. Apr 13 '12 at 3:00
  • 1
    $\begingroup$ Are there some useful guidelines on how to approach such problems? I am completely lost when I see a question that asks me to prove it is NPC. How should I approach them? $\endgroup$ – Anonymous Apr 13 '12 at 8:17
43
$\begingroup$

There is no magic bullet; NP-hardness proofs are hard. However, there is a general framework for all such proofs. Many students who struggle with NP-hardness proofs are confused about what they're supposed to be doing, which obviously makes it impossible to figure out how to do it. So here is what to do to prove a problem NP-hard.

First, unless you're just doing homework, you have to decide which NP-hard problem to reduce to your problem. This is largely a question of "smell". If the number 3 appears anywhere in the problem statement, try reducing from $\mathsf{3SAT}$ or $\mathsf{3Color}$ or $\mathsf{3Partition}$. (Yes, I'm serious.) If your problem involves finding an optimal subsequence or permutation or path, try reducing from $\mathsf{HamiltonianCycle}$ or $\mathsf{HamiltonianPath}$. If your problem asks for the smallest subset with a certain property, try $\mathsf{Clique}$; if it asks for the largest subset with a certain property, try $\mathsf{IndependentSet}$. If your problem involves doing something in the plane, try $\mathsf{PlanarCircuitSAT}$ or $\mathsf{PlanarTSP}$. And so on. If your problem doesn't "smell" like anything, $\mathsf{3SAT}$ or $\mathsf{CircuitSAT}$ is probably your best bet.

Obviously, you need to already know precisely how all these problems are defined, and the simpler the problem you reduce from, the better. So as cool as the result might look in the end, I don't recommend reducing from $\mathsf{Minesweeper}$ or $\mathsf{Tetris}$ or $\mathsf{OneCheckersMove}$ or $\mathsf{SuperMarioBros}$.

Second, the actual reduction. To reduce problem X (the one you know is NP-hard) to problem Y (the one you're trying to prove is NP-hard, you need to describe an algorithm that transforms an arbitrary instance of X into a legal instance of Y. The reduction algorithm needs to do something specific with each "feature" of the X-instance; the portion of the output for each "feature" is usually called a gadget.

But what's a feature? That depends on problem X. For example:

  • To transform an instance of $\mathsf{3SAT}$, you'll need a gadget for each variable and for each clause in the input formula. Each variable gadget should have two "states" that correspond to "true" and "false". Each clause gadget should also have multiple "states", each of which somehow forces at least one of the literals in that clause to be true. (The states are not part of the output of the reduction algorithm.)

  • To transform an instance of $\mathsf{3Color}$, you'll need a gadget for each vertex and each edge of the input graph, and another gadget to define the three colors.

  • To transform an instance of $\mathsf{PlanarCircuitSat}$, you'll need a gadget for each input, for each wire, and for each gate in the input circuit.

The actual form of the gadget depends on problem Y, the one you're reducing to. For example, if you're reducing to a problem about graphs, your gadgets will be small subgraphs; see the Wikipedia article. If you're reducing to a problem about scheduling, each gadget will be a set of jobs to be scheduled. If you're reducing to a problem about Mario, each gadget will be a set of blocks and bricks and Koopas.

This can get confusing if both problems involve the same kind of object. For example, if both X and Y are problems about graphs, your algorithm is going to transform one graph (an instance of X) into a different graph (an instance of Y). Choose your notation wisely, so that you don't confuse these two graphs. I also strongly recommend using multiple colors of ink.

Finally, your reduction algorithm must satisfy three properties:

  • It runs in polynomial time. (This is usually easy.)

  • If your reduction algorithm is given a positive instance of X as input, it produces a positive instance of Y as output.

  • If your reduction algorithm produces a positive instance of Y as output, it must have been given a positive instance of X as input.

There's an important subtlety here. Your reduction algorithm only works in one direction, from instances of X to instances of Y, but proving the algorithm correct requires reasoning about the transformation in both directions. You must also remember that your reduction algorithm cannot tell whether a given instance of X is positive or negative—that would require solving an NP-hard problem in polynomial time!

That's the what. The how just comes with practice.

$\endgroup$
  • 5
    $\begingroup$ For reductions from $3SAT$ (and generally problems which has similar "local/global structure") it might be a good idea to try to do it first for a single clause instances of $3SAT$. That can give you an idea about what gadget you need to use for clauses. After finding out the gadget for a clause, your reduction will put one of these gadgets for each clause and then somehow enforce the global condition (i.e. the truth values for occurrences of a variable appearing in different clauses should be consistent, a propositional variable $p$ cannot be $true$ in one clause and $false$ in another). $\endgroup$ – Kaveh Apr 13 '12 at 19:36
  • 1
    $\begingroup$ Regarding "If your reduction algorithm produces a positive instance of Y as output, it must have been given a positive instance of X as input": Although it would seem more intuitive to write this condition as "If your reduction algorithm is given a negative instance of X as input, it produces a negative instance of Y as output", notice that these two conditions are equivalent, and how JeffE has written it usually makes constructing the proof much easier, since in each case you "have something" (either the positive instance of X, or the positive instance of Y) to work with. $\endgroup$ – j_random_hacker Mar 9 '18 at 14:56
10
$\begingroup$

JeffE outlines the most common strategy: know lots of NP-complete problems, find one that fits very well and make the easy reduction.

Another valid strategy is to always use 3SAT (or any other problem). This might make some reductions more intricate, but the upside is that you have lots of experience expressing satifiability in other types of problems. So you save the time of finding a good reduction partner (including dead-ends) and hope that your experience will allow you to do the reduction quickly even if it is harder.

This approach has some meta beauty, too: (3)SAT is one of the few problems for which NP-completeness has been proven (almost) directly. Therefore, relying only on that proof keeps your "proof tree" flat, avoiding long chains of reductions.

$\endgroup$
  • 3
    $\begingroup$ Directly proving that the Bounded Halting problem is NP-complete when the bound is given in unary is not too hard, and is an easy way of proving that some NP-complete problem exists, even though the problem itself is rather useless to reduce from. $\endgroup$ – Alex ten Brink Apr 14 '12 at 18:25
  • 3
    $\begingroup$ I am not sure about the claim that it is the only problem that has been proven to be NP-complete directly. In fact if you interpret it in a strict sense then it is definitely false. Cook's 1971 paper talks about TAUT not SAT (he uses Cook reductions, not Karp reductions) (it is an easy observations that the proof also proves that SAT is NP-complete under Karp reductions). $\endgroup$ – Kaveh Apr 15 '12 at 1:44
  • $\begingroup$ @Kaveh Huh? Tautology is Co-Np complete and therefore not known to be in NP(-complete). I didn't read Cook's paper though. $\endgroup$ – Albert Hendriks May 5 '18 at 22:03
  • 1
    $\begingroup$ @Albert, well you should read it then. With Cook reductions you cannot distinguish between NP and coNP. $\endgroup$ – Kaveh May 5 '18 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.