Oracles and Turing reductions

Introduction

Turing reduction

Treat other problem as a black box, returned from oracle.

If A can be Turing reduced to B, then if there is an algorithm for B, there is an algorithm for A.

If A is Turing reducible to B and B is Turing reducible to A then the problems are Turing equivalent.

Note that this is different to polynomial Turing reduction (Cook reduction).