Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question

migrated from Mar 1 '11 at 1:56

This question came from our site for theoretical computer scientists and researchers in related fields.

Why did you down vote it? Its a pretty hard question.. – Adibe7 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. – user489 Feb 28 '11 at 21:52
ok, i'll rewrite it – Adibe7 Feb 28 '11 at 21:53
better? i really thought about it for a long time.. really non trivial one. – Adibe7 Feb 28 '11 at 22:01
@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
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.