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.

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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.