Linear Reduction

A problem X, reduces to another problem, Y, if we can efficiently transform instances of the problem X into instances of the problem B in such a way that solving the transformed instances yields the solution to the original instance.

Formal Definitions

The problem A is linearly reducible to perform B, Denoted A ≤ ^lB, if the existence an algorithm for B that runs in a time O(t(n)) for any function t(n) implies that there exists an algorithm for A that also runs in a time O(t(n)).

If A ≤ ^lB and B ≤ ^lA then A and B are linearly equivalent and denoted A == ^lB.

Also, the linear reduction are transitive:
        if A ≤ ^lB and B ≤ ^lC, then A ≤ ^lC.

Linear equivalence are transitive reflexive and symmetric. (Hence, equivalent.)