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

References