# Reduction

Example: Coloring $\to$ SAT

Support there's a poly-time algorithm for SAT, we want to use it to construct a algo for coloring. Let $I$ be the input for coloring, we need

I -> convert to input of SAT, f(I) -> run SAT -> convert to output of coloring, h(S)

We want to define $f$ and $h$ and show they run in poly-time.

- $f$ takes the input of coloring, returns the input for SAT
- $h$ takes the output of SAT, returns the output of colorings

## NP-completeness proof

Example: independent sets (IS)

Need to show:

- $IS\in NP$
- For all problem $A\in NP$, we can convert A to IS

We know SAT is NP-complete, then we automatically have $A$ to SAT and we only need to show SAT $\to$ IS reduction.