Skip to main content
Computer Science

Return to Question

edited title
Source Link
Juho
Juho
  • 22.8k
  • 7
  • 62
  • 117

Difference between 'Reductions'reductions in algebraic problems vs "Reductions"versus reductions in Computational Intractabilitycomputational intractability

When I read about NP-completeness for the first time, I really wondered why is the concept of Reductionsreductions 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 Algebraalgebra 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 Intractabilitycomputational intractability same as that in above algebraic theory?" If not, how isare the reductions in CI theory different?

Difference between 'Reductions' in algebraic problems vs "Reductions" in Computational Intractability

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?

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?

Source Link
Sravan
Sravan
  • 121
  • 1

Difference between 'Reductions' in algebraic problems vs "Reductions" in Computational Intractability

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?