Skip to main content
2 of 2
edited title
Juho
  • 22.8k
  • 7
  • 62
  • 117

Difference between reductions in algebraic problems versus reductions in computational intractability

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?

Sravan
  • 121
  • 1