HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Relation beetween log-space reduction and polynomial time reduction

Submitted by: @import:stackexchange-cs··
0
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.

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}$.

Context

StackExchange Computer Science Q#99578, answer score: 2

Revisions (0)

No revisions yet.