# Logarithmic space difference between deterministic and non-deterministic algorithms

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!

• – 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