Difference between reductions in algebraic problems versus reductions in computational intractability

Question

When I read about 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 the 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 are the reductions in CI theory different?

Answer 1

Reductions in computational complexity are similar to the reduction you described, but are usually given with bounds on the time or space. To be useful, these bounds are usually inconsequential (ie. the same or smaller) to the bounds of solving the problem.

Reductions in computational complexity are about converting one problem to another equivalent one. Usually one would also give bounds on how hard (how much time/space) a reduction takes as well. For example, all NP-complete problems have reductions to each-other, and their reductions are polynomially bounded. Since algorithms solving NP-complete problems are suspected to take exponential time on a deterministic Turing machine, the polynomial time reductions are inconsequential (compared with the time of actually solving the reduced problem), and thus these reductions make all of the NP-complete problems essentially equivalent. There can reductions between problems in other classes of complexity as well, and to be useful they would likely be bounded by something considered inconsequential to solving them.

Answer 2

We are interested in reductions (relative hardness) because of our inability to prove absolute hardness results.

For example, say you give me a problem to solve. After spending time on it, I am unable to come up with an efficient algorithm for it. Maybe I'm too dumb to come up with an algorithm, or maybe a (fast) algorithm doesn't exist. I would like to back up my excuse somehow. If I can reduce a known hard problem $X$ to the problem you gave me, I'm showing that $X$ is at least as hard the problem you gave me. That means that maybe I'm not that dumb; other people have not been able to solve the problem either.

Answer 3

Reductions are useful in studying computability not so much to prove that problems are computable (although that is also done), but to prove that problems are not computable.

Used to prove incomputability, a reduction proof is a particular kind of proof by contradiction. You take your problem P and a known incomputable problem X, and you show that if you had an algorithm that computed solutions to P you could use it to compute solutions to X. Since we already know that there there does not exist a method for computing solutions to X this proves that there cannot exist a method for computing solutions to P.

This isn't really "different" from the kind of reduction you're talking about in algebra; if you have an algebraic problem P and you show that a solution to P could be used to find a solution to X, and you already know that X has no solutions, then this would show that P has no solutions either. But you usually think about the notion of "problem" slightly differently in algebra, as well as about the way you use "reductions".

My experience in mathematics was that you're usually aiming to turn an equation you don't know how to solve in to a form that you do know how to solve, in order to find a particular solution (possibly with unknown constants). Whereas a "problem" in computer science is a specification for producing an output (usually yes/no) on instances of an infinite family of inputs.¹ And for computability purposes you're interested not in finding any particular solution, but in showing whether or not there exists an algorithm that can compute the solution for any input.

Basically it has turned out that a large number of computational problems have been difficult to directly prove incomputable, but are relatively easy to reduce to known incomputable problems. Variants on the Halting Problem are particularly rich sources of undergraduate-level incomputability proofs. I'm not aware that this is done nearly so much in mathematics, hence the difference in emphasis.

---

¹ Any problem that only has one instance (e.g. one specific algebraic formula, like 2x^8 - 9 = 83) is completely uninteresting from the point of view of computability theory, because finite problem series are all trivially computable by a stupid algorithm that simply has all the solutions hard-coded and immediately prints the one corresponding to its input.

My Theory of Computation lecturer liked to joke that the problem "does God exist?" is computable; the program that computes the solution is either a single-state DFA that immediately accepts, or a single-state DFA that immediately rejects. We just don't know which one it is!