Cook Reduction

computation

Definition

Cook Reduction

A Turing reduction with $M^B$ that runs in polynomial time (counting each oracle call as one step), we write $A{\le }_{P}B$ and call it a polynomial-time Turing (Cook) reduction.