CODEWITHSUNDEEP
complexity-theorygraph-algorithmreductionnp-completenp
Monalizza
Monalizza

Reputation: 27

Why do we get to pick the source in an NP-completeness reduction?

We know that to prove that problem A is NP-complete, we have to find a polynomial time reduction from NP-complete problem B to this problem A.

For example, we can do these reductions:

 SAT ---> clique
 SAT ---> independent set
 Independent set ---> Vertex Cover

Why is it that we get to choose which NP-complete problem we use as the source of the reduction? Are all NP-complete problems reducible to each other, and we just need to choose the one that is easier to show the reduction?

I mean it was easy to show the reduction from SAT to clique. However, I don't know how to show the reduction from SAT to Vertex Cover, but I know how to reduce from Independent Set to Vertex Cover. Is it in principle possible reduce each NP-Complete to every other NP-Complete, but we just use the easiest one?

Upvotes: 2

Views: 263

Answers (1)

templatetypedef
templatetypedef

Reputation: 373082

A problem is NP-complete if

  • it's in NP, and
  • every problem in NP is polynomial-time reducible to it.

This means that if you take any two NP-complete problems, you're guaranteed that they're polynomial-time reducible to one another, even if you don't know precisely what that reduction is going to look like.

You asked why you get to pick which NP-complete problem to use as the source of a reduction when proving NP-completeness. The reason is that once you've shown that some NP-complete problem A reduces to an NP problem B, you can conclude that every NP-complete problem C reduces to B, since C reduces to A and A reduces to B. In other words, if you prove that a problem is NP-complete by reducing any known NP-complete problem to it, you could have in principle reduced every NP-complete problem to it. You're just keeping things easy by reducing from a problem that makes the reduction easiest to do.

It can be pretty tough in practice to do a reduction if you pick the wrong NP-complete language as your source. To get a sense of why this is, think about how the proof of Cook-Levin theorem (that SAT is NP-complete) works. To show that you can reduce any NP problem to SAT, you start with a polynomial-time, nondeterministic Turing machine for that problem, then use that to construct a massive propositional formula that basically says "there is some computation of this TM that accepts its input string." This is great in theory, but in practice this is a horrid reduction that would be almost utterly incomprehensible to anyone who looked at it. Any time you're proving NP-completeness of a problem by doing a reduction from a known NP-complete problem, think of it as finding a shortcut to skip a really tough proof - if you can find something nice and simple, you're skipping a behemoth of a reduction.

Upvotes: 1

Related Questions