Skip to main content
formatting
Source Link
xskxzr
  • 7.6k
  • 5
  • 23
  • 47

I read somewhere that given two languages $A$ and $B$, if $A \le_{log} B$$A \le_{\log} B$, then $A \le_P B$ (with $\le_{log}$$\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.

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.

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.

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

Could someone help me with that please.

Thanks.

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.

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.

Bumped by Community user
Bumped by Community user
Source Link

Relation beetween log-space reduction and polynomial time reduction

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.