Adversary Argument

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.)