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!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.