3
$\begingroup$

i'm trying to solve this question: Given a turing machine that is decidable by at most 50 * n^4 steps, can we build a dif algorithm that can decide it in n^4 steps?

Me and my friends thought about it, and we coulnd't get it right. Some points we had in mind: 1. if you can reduce the overall cost by 50 somehow, couldn't you reduce it over and over again? 2. we tried to think about algorithms that require 50*n^4 moves (at most) and we thought about this language: string str is in A if str.GetHashCode().GetHashCode()... 50 times is even. do you think this algorithm is unreducable?

thanks for the help!

  • 0
    @Adibe7, I think [the wiki page for linear speed-up](http://en.wikipedia.org/wiki/Linear_speedup_theorem) should answer your question, but if you want I can remigrate the question to Math.SE from here.2011-02-28

1 Answers 1

3

You can find the answer on Wikipedia. If you don't want to look it up, think how can you build a TM then executes $50$ steps of the old machine at once; you may need some bootstrapping phase.