Problem Reductions

Prof. GNF @ Purdue provided one of the best learning opportunities I ever had in CS 381 - Algorithms. A particular section that I was particularly attracted to was problem reductions. Basically, you want to reduce 1 problem to another so you can use a previous solution to solve it.

Reductions were (I am using the past tense since I haven't picked such problems up in the recent past) central to proving NP Completeness. One of the rather interesting pitfalls undergrads @ Purdue seem to be facing is in understanding the reduction process.

In particular, I could boil their confusion down to something like this:

I know something about problem "a" (in this case, "a" is NP-Complete). So, if I need to figure something out about the NP-Completeness of some problem "b", I will make a sincere effort to solve it using "a". If I solve it using "a", "b" is NP-Complete.

WRONG! I am a math major and I see the temptation to use a known problem's solution to make some inferences about an unknown problem but seriously that is not what you are looking for here.

The fail in this approach is that no one is able to grasp the correct trail of thought. This is how you think:

I have some information about the perf of a, let me use that to make some inferences about b.

How do you infer stuff about b using a?

Let us say we are faced with the following problem:

You are sitting in level 1 of the Lawson CS Building. Your goal is to go to the basement.
Last week, you figured out:

  • How to get to Level 2 from Level 1 (takes 2 minutes)
  • How to get from Level 1 to the basement.  (takes 4 minutes)

So, here's a diagram and a problem description:

To be solved: Get to basement from level 1

What we know: Getting to level 2 from level 1 (takes 2 minutes), Getting to basement from level 2 (takes 4 minutes)

So, if you apply the ass-backwards thinking that most people seem to do, we would go from level 1 to level 2 and then go to the basement from there in a grand total of 6 minutes.

Ok, what then? Well, using the problem solving structure you were applying before, you ended up concluding that going from level 1 to the basement will take 6 minutes (just like how you concluded that b is now NP-Complete).

But that is dead wrong. From what we see, the path you choose to solving a problem tells you nothing about how easily the problem can be solved!
When you chose to solve "b" using "a", you made a (potentially stupid) choice about how to solve "b". Possibly "b" could have a polynomial time solution and you still chose to apply a solution to it that won't finish till your grandkids are born.

Here is how you approach that problem:

  • You know something about "a". More precisely, you know "a" is NP-Complete. You know that there is no polynomial time algorithm known for "a".
  • You then decide, "Hey, let me see if I can solve "a" using "b".
  • If you figure out you can solve "a" using "b", then obviously, the theoretical lower bound you computed for "a", holds for "b".  You now know that "b" cannot do better than "a" (if it did, you might have proved P = NP :) ).
  • Well, now we know that since "b" cannot do better than "a", "b" is NP-Complete    (You still need to prove that "b" is in NP but I am assuming you know how to do that)

That wasn't so hard, was it?

Leave a Reply