# Reductions

• A typical way to solve problems, is to reduce a new problem to a previously solved problem

## Many-one Reduction

• Many-one reduction: An instance of a new problem is expressed as an instance of a prior problem for which the solution is then interpreted in terms of the new problem
• $$A$$ is many-one reducible to $$B$$, written $$A \leq_{m} B$$, if there exists a computable function $$f$$ such that $$x \in A$$ iff $$f(x) \in B$$
• The function $$f$$ is called the transformation function

## Turing Reduction

• Turing reduction: A different way to solve a new problem is to use a subroutine that solves a prior problem
• For example, we can solve an optimization problem by repeatedly calling a subroutine which solves the correspondig decision problem of a certain bound
• $$A$$ is Turing reducible to $$B$$, written $$A \leq_{T} B$$, if $$A$$ can be decided by a deterministic oracle Turing Machine $$M$$ using $$B$$ as its oracle
• The oracle for $$B$$ models a hypotheical efficient subroutine for $$B$$
• The oracle can be called a polynomial number of times
• Many-one reductions can be regarded as restricted variants of Turing reductions where the oracle can only be called once and the value returned is exactly the result from the oracle

## Polynomial-time Reduction

• If the reduction consumes too much time or space, then the reductions are not helpful
• That’s why there are also resouce-bounded reductions
• $$A$$ is Karp reducible to be $$B$$, written $$A \leq_m^p B$$, if the transformation function $$f$$ is computable deterministically in polynomial time
• The term “polynomial-time reduction” usually refers to Karp reductions
• $$A$$ is Cook reducible to $$B$$, written $$A \leq_T^p B$$, if the oracle Turing Machine has polynomial time complexity