Reductions

Turing Reductions

• $A{\le }_p^{T}B⟺$ there is a poly-time algorithm $M^B$ with oracle access to $B$ such that $M^B$ solves $A$
  • Oracle access: Algorithm $M^B$ can query the oracle on inputs to problem B, and each query is counted as 1 unit of time

Karp Reductions

• $A{\le }_{p}B⟺$ there is a poly-time computable function $f:A\to B$ such that
  • x is a YES instance of $A⟺f(x)$ is YES instance of $B$

NP

1. NP-Completeness
2. NP-Hardness