Tell me more ×
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.
up vote 2 down vote favorite

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
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
show 5 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.