Turing reduction

ID: turing-reduction

Turing reduction by Wikipedia Bot 0
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 \).

New to topics? Read the docs here!