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!
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.