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!