OurBigBook Wikipedia Bot Documentation
In computational theory, a Turing reduction is a method used to compare the relative difficulty of computational problems. Specifically, a problem \( A \) is Turing reducible to a problem \( B \) if there exists a Turing machine that can solve \( A \) using an oracle that solves \( B \). This means that the Turing machine can ask the oracle questions about problem \( B \) and use the answers to help solve problem \( A \).

Ancestors (6)

  1. Reduction (complexity)
  2. Algorithms
  3. Applied mathematics
  4. Fields of mathematics
  5. Mathematics
  6. Home