## Showing & Proving Reductions 1. Creating reduction algorithm - create algorithm F where - F : (input of A) $\rightarrow$ (input of B) 2. Proving the algorithm works - prove ($\exists$ a solution to input $I$ of A) $\implies$ ($\exists$ a solution to modified input $F(I)$ of $B$) - prove ($\exists$ a solution to modified input $F(I)$ of $B$) $\implies$($\exists$ a solution to input $I$ of A) ## General Notes - in simple terms, reducing $A$ to $B$ enables you to solve the problem $A$ using $B$ as a subroutine - solving $A$ effectively becomes solving $B$ - functions $f$ & $h$ on both ends act to keep "worlds" of $A$ & $B$ separate - inside the box only $B$ specific formulations allowed - outside the box only $A$ specific formulations allowed - a reduction from problem $A$ to problem $B$ is a polynomial time algorithm $f$ that transforms any instance $I$ of problem $A$ into an instance $f(I)$ of problem $B$ - together, with another polynomial time algorithm $h$ that maps any solution $S$, of problem $B$ (inputted with $f(I)$), back into a solution $h(S)$ of $I$ ![[CleanShot 2024-04-20 at 16.46.17@2x 1.png]] - $\exists$ efficient algorithm for $B$ $\implies$ $\exists$ efficient algorithm for $A$ - $f(I)$ has no solution $\implies$ $i$ has no solution - In A to B reduction, B is at least as hard as A, A's complexity is capped at B's https://people.eecs.berkeley.edu/~vazirani/algorithms/chap8.pdf