Informatik

Was ist eine Turing-Reduktion?

Ein Problem $A$ ist Turing-reduzierbar auf $B$, wenn $A$ mit Zugriff auf ein Orakel für $B$ gelöst werden kann.

Sie ist allgemeiner als many-one-Reduktion.