Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I had an interview today, and the interviewer has told me about a theorem (of someone called Hill- or Hell-something) which states that for a non-deterministic algorithm there exists a deterministic algorithm of some time complexity and a space complexity of no more than the original space complexity times log(n).

I am looking for that theorem (couldn't find it on Google). Thanks!

share|improve this question
Savitch's theorem? –  Pratik Deoghare Dec 23 '12 at 9:06
$\mathsf{NSpace}(f(n)) \subseteq \mathsf{DSpace(f^2(n))}$ and nothing better is known (AFAIK). –  Kaveh Dec 23 '12 at 9:20
note that if $f(n)=\lg n$, then $f^2(n)=\lg n \times \lg n$. –  Kaveh Dec 23 '12 at 9:21
See this question cstheory.stackexchange.com/q/2426/612. –  Pratik Deoghare Dec 23 '12 at 9:24
@PratikDeoghare Post as an answer? –  Yuval Filmus Dec 23 '12 at 19:19

Your Answer


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

Browse other questions tagged or ask your own question.