When I read NP-completeness for the first time, I really wondered why is the concept of Reductions given such high emphasis, after all we have been looking at concepts such as reductions and 'special case of one another problem' in mathematics since elementary algebra. What I mean by reductions in Algebra is following -

Problem 1: Find value of x such that $x^2+ax+b=0$

Problem 2: Find value of x such that $(x+m/n)^2=0$

We can go on proving both the problems are same and one solution can be translated to another.

My question is that "Is the concept of reductions in Computational Intractability same as that in above algebraic theory?" If not, how is the reductions in CI theory different?


First, I agree that there is a similarity, and perhaps complexity could be more easily taught if people observed it, and used that when explaining reductions in complexity. Neat!

Second, there's a little bit of a slippery slope here, because really any proof system that people would actually use contains a lot of steps that look like "$A \iff B$", so we might say that most or all proofs have reductions. The part about complexity reductions and algebraic reductions that makes them beautiful is that you can compress $A \iff B \iff \cdots \iff Z$ to $A \iff Z$ and argue directly by the properties of $A$ and $Z$, without needing to justify the intermediate steps. So, I'll stick to that kind of more "beautiful" reduction.

I think there's two parts to why these reductions are defined freshly. First, in complexity there's usually a time bound, so it's not just about saying "$A \iff B$", but saying "From $A$ I can generate a $B$ very quickly such that $A \iff B$." When we use reductions in other parts of math, we pay less attention to the time to generate it. If you can generate it, then go for it, and you can use that in your proof.

I think the second reason may be that reductions outside of complexity are one of many available tools, but for parts of complexity reduction is the only tool. In algebra, there are almost always (always?) ways to argue a fact without using a reduction; certainly without using a major, significant, beautiful reduction. In complexity, the way that many classes are defined, you cannot show membership in a class without forming a reduction. This means many people might go through algebra and not see the concept of reductions there. So if they learn complexity theory they must be taught this concept, and the best thing a teacher/book can do at that point is show the concept to everyone.


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