1 Answers
In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any k-tape Turing machine solving a problem in time f, there is another k-tape machine that solves the same problem in time at most f/c + 2n + 3, where k > 1.If the original machine is non-deterministic, then the new machine is also non-deterministic.The constants 2 and 3 in 2n + 3 can be lowered, for example, to n + 2.
8 views
Answered