Reduction

A reduction translates one problem to another. Using reductions we can show that two problems are exactly the same, just stated in another way. Using this, we can identify the hardest problems in Non-deterministic Polynomial Time. A reduction from search problem A to B is

1. A polynomial-time algorithm f that transforms any instance I of A into instance $f(I)$ of B
2. A polynomial-time algorithm h that maps any solution S of $f(I)$ back into a solution $h(S)$ of I

If there is a reduction form A to B, then an algorithm for B can be used to solve A.

Examples

All of NP → Circuit SAT → SAT → 3SAT → 3D Matching → ZoE → HC / ILP / Subset Sum → Traveling Salesman Problem because these are all NP Complete problems.

Hamiltonian Paths → HC
You can reduce the Hamiltonian ST problem to a HC problem by adding a vertex x between s and t, where the path is $s\to x\to t$. Then solve HC.

HC → Traveling Salesman Problem
Here, you basically allocate a budget of $|V|$, and assign each edge length to be 1, if the edge is in E, and $1+\alpha$ ($\alpha >0$) if it is not in E (we need to add this edge to complete the graph). Then, if there is a HC, we will be able to find a tour that is within our budget, otherwise we will not be able to.

SAT → Directed HC
This is a much more complicated reduction.
Based off of our SAT formula, we construct a chain that is a directed HC where each direction that you traverse the chain corresponds to True or False. The length of the chain / gadget is related to the number of times $x_i$ appears in the SAT formula.

Then we chain up $x_2,\dots ,x_n$ to the end vertex and well have an edge from our end to our start to complete the cycle. We can further reduce this to undirected HC by replacing each vertex with three vertices, $v_{in}$, $v$, $v_{out}$.

Any Problem in NP → SAT

1. This uses a generalization of SAT called Circuit SAT. Then we reduce Circuit SAT to SAT.
2. Circuit SAT to SAT represents the output of each gate with a variable $g_i$, then we create a SAT formula such that the gate logic between inputs and outputs is captured when formula is true.
3. We replace each gate in the circuit with the appropriate SAT clause
4. Now we need to reduce every problem in NP to Circuit SAT
   1. Taking a problem A in NP, there is an algorithm C that checks if S is a solution to problem instance I of A and C runs in polynomial time
   2. But any polynomial-time algorithm can be written as a circuit because the algorithm runs on a computer and a computer is ultimately a boolean combinational circuit, implemented on a chip
   3. Therefore, any polynomial time algorithm can be rendered as a boolean circuit where there are polynomially many copies of the computer’s circuit, one per unit of time. The values of gates in copy t used to compute values of gates for copy t+1
   4. Therefore, we can write C as a boolean circuit which is a circuit SAT instance for problem A which reduces to SAT