3

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!

Adibe7
  • 131
  • 1
    Why did you down vote it? Its a pretty hard question.. –  Feb 28 '11 at 21:48
  • It's not a good idea for the body of your question to be exactly the same as the title. It really makes it look like you haven't put in much effort to formulate a good question. Add to that the fact that this is obviously homework, and a lot of people are going to assume you copied it directly from your assignment. Put in some effort and show us what you've come up with on your own. –  Feb 28 '11 at 21:52
  • ok, i'll rewrite it –  Feb 28 '11 at 21:53
  • better? i really thought about it for a long time.. really non trivial one. –  Feb 28 '11 at 22:01
  • Your edit increased the quality of the question by at least 50 times. ;) –  Feb 28 '11 at 22:02
  • thanks. Now i hope i could talk with someone about it and understand how to answer it :) –  Feb 28 '11 at 22:05
  • Now that it's improved, I'm going to migrate it over to the CS Theory site where it belongs. –  Feb 28 '11 at 22:09
  • 4
    @Bill the Lizard, this is not research level question. Check the speedup theorem on wiki. Please do not migrate this kind of questions directly to cstheory, migrate them first to Math.SE. cstheory is for research level questions. Thanks. – Kaveh Feb 28 '11 at 22:27
  • @Kaveh: Sorry about that. I forgot to read the FAQ before migrating. Thanks for the link, though. That should answer his question. –  Feb 28 '11 at 22:47
  • @Bill the Lizard, no problem. :) – Kaveh Feb 28 '11 at 22:48
  • @Adibe7, I think the wiki page for linear speed-up should answer your question, but if you want I can remigrate the question to Math.SE from here. – Kaveh Feb 28 '11 at 22:51

1 Answers1

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.

Yuval Filmus
  • 57,157