Reduction (complexity)
In computational complexity theory, reduction is the transformation of an instance of one problem into an equivalent instance of another problem.
Roughly speaking, if a problem A reduces to a problem B, this means A is easier to solve than B, and B is harder to solve than A. This is because if have a good solution to problem B, we can transform problem A into an instance of problem B, and then solve it using this solution. For the same reason, if we provably don't have a good solution to problem A, then we can't have a good solution to problem B, because if we did this would yield a good solution for problem A.
Reduction is used in the definition of complexity class if every problem in the class reduces to that problem.
The appropriate notion of reduction depends on the complexity class being studied. When studying the complexity class P and harder classes, polynomial-time many-one reduction is used. When defining classes in the polynomial hierarchy, polynomial-time Turing reduction is used. When studying classes within P (such as NC and LOGSPACE), logarithmic-space many-one reduction is used. Reduction is also used in computability theory to show that problems are or are not solvable by a computer.
This article is a stub. You can help BambooWeb by .
