## 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 ≤ ^{l}B,
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 ≤ ^{l}B and B ≤ ^{l}A then A and B are linearly
equivalent and denoted A == ^{l}B.

Also, the linear reduction are transitive:

if A ≤ ^{l}B and B ≤ ^{l}C,
then A ≤ ^{l}C.

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