patternMinor
Relation beetween log-space reduction and polynomial time reduction
Viewed 0 times
spacelogpolynomialbeetweentimereductionandrelation
Problem
I read somewhere that given two languages $A$ and $B$, if $A \le_{\log} B$, then $A \le_P B$ (with $\le_{\log}$ the log-space reduction and $\le_P$ the polynomial time reduction), but I'm not sure about the proof.
Could someone help me with that please.
Could someone help me with that please.
Solution
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}$.
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}$.
Context
StackExchange Computer Science Q#99578, answer score: 2
Revisions (0)
No revisions yet.