3
$\begingroup$

Is it true that adding to a Turing-machine-equivalent an "oracle" calculating any polynomially calculable (in this machine) function using some other nonzero polynomial time than this machine itself could do, leaves the new Turing machine equivalent (in the sense that polynomial algorithms remain polynomial and exponential ones remain exponential)?

$\endgroup$
3
$\begingroup$

Yes. You can replace the oracle with subroutine calls to the polynomial-time implementation of the oracle. Or, to put it another way: $P$ is closed under composition.

The running time remains polynomial: if the original Turing machine used $p(n)$ steps, and the subroutine takes $q(n)$ steps, then the resulting machine will use at most $p(n) + q(p(n))$ steps, which is upper-bounded by a polynomial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.