patternMinor
Is it OK to change any polynomial time to another polynomial time without breaking equivalency of Turing machines?
Viewed 0 times
withoutpolynomialanytimebreakinganothermachinesturingequivalencychange
Problem
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)?
Solution
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.
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.
Context
StackExchange Computer Science Q#139006, answer score: 3
Revisions (0)
No revisions yet.