1
$\begingroup$

I read somewhere that given two languages A and B, if A <=(log) B, then A <=(P) B (with <=(log) the log-space reduction and <=(P) the polynomial time reduction), but I'm not sure about the proof.

Could someone help me with that please.

Thanks.

$\endgroup$
1
$\begingroup$

Every terminating Turing machine running in logarithmic space terminates in polynomial time. This is because the number of configurations in a logarithmic space Turing machine is polynomial; a logspace Turing machine running longer than the number of configurations will necessarily repeat a configuration, and so will never terminate.

More generally, $\mathsf{SPACE}(f(n)) \subseteq \mathsf{TIME}(2^{O(f(n))})$ for similar reasons. This gives not only $\mathsf{L} \subseteq \mathsf{P}$ but also $\mathsf{PSPACE} \subseteq \mathsf{EXPTIME}$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.