Key Reduction Techniques to Know for Computational Complexity Theory

Reduction techniques are key tools in Computational Complexity Theory, helping us understand how problems relate to each other. They allow us to transform one problem into another, revealing insights about their complexity and classifying them within P, NP, and beyond.

1. Many-one reductions (Karp reductions)

   • A type of reduction where a problem A can be transformed into problem B in a single step.
   • If A is reducible to B, and B is in NP-complete, then A is also NP-complete.
   • The transformation must be computable in polynomial time.

2. Turing reductions (Cook reductions)

   • Allows for multiple calls to the oracle (the problem being reduced to) during the computation.
   • More powerful than many-one reductions, as it can use the solution of B multiple times.
   • If A is Turing reducible to B, and B is decidable, then A is also decidable.

3. Polynomial-time reductions

   • A general class of reductions where the transformation from one problem to another is computable in polynomial time.
   • Essential for classifying problems in complexity classes like P, NP, and NP-complete.
   • Ensures that the complexity of the original problem is preserved in the transformed problem.

4. Logarithmic-space reductions

   • Reductions that can be performed using logarithmic space in the size of the input.
   • Important for understanding the relationships between complexity classes like L (logarithmic space) and NL (nondeterministic logarithmic space).
   • Helps in analyzing problems that can be solved efficiently in terms of memory usage.

5. Mapping reductions

   • A specific type of many-one reduction where the transformation is a function that maps instances of one problem to instances of another.
   • The mapping must be computable in polynomial time and must preserve the yes/no nature of the problems.
   • Useful for establishing the hardness of problems in complexity theory.

6. Truth-table reductions

   • A type of reduction that allows for parallel queries to the oracle, with a fixed number of queries.
   • The decision for the original problem is based on the answers to these queries.
   • Important for understanding the relationships between complexity classes, particularly in the context of NP and co-NP.

7. Randomized reductions

   • Reductions that incorporate randomness in their computation process.
   • Can be used to show that certain problems remain hard even when randomized algorithms are applied.
   • Important for the study of complexity classes like BPP (bounded-error probabilistic polynomial time).

8. Approximation-preserving reductions

   • Reductions that maintain the quality of approximate solutions between problems.
   • If a problem A can be approximated within a certain factor, then problem B can also be approximated within a similar factor.
   • Useful in the context of optimization problems and understanding their approximability.

9. Gap-preserving reductions

   • Focus on preserving the gap between the optimal solution and the approximate solution.
   • If a problem A has a certain gap, then problem B will also exhibit a similar gap.
   • Important for analyzing the hardness of approximation and understanding the limits of efficient algorithms.

10. Parsimonious reductions

    • A type of many-one reduction that preserves the number of solutions to the problem.
    • If A has k solutions, then B will also have k solutions after the reduction.
    • Useful in counting problems and understanding the relationship between decision and counting complexity.