<p>One simple consequence is $\mathbf{P}/\text{poly} = \mathbf{L}/\text{poly}$. Proof: For any language $A \in \mathbf{P}/\text{poly}$, there is a language $B \in \mathbf{P}$ and a sequence of polynomial-length advice strings $y_1, y_2, y_3, \dots$ such that $x \in A \iff (x, y_{|x|}) \in B$. By assumption, there is a language $C \in \mathbf{L}$ and a sequence of polynomial-length advice strings $z_1, z_2, z_3, \dots$ such that $(x, y) \in B \iff (x, y, z_{|(x, y)|}) \in C$. This implies $A \in \mathbf{L}/\text{poly}$; the advice string for $x$ is $(y_{|x|}, z_{|(x, y_{|x|})|})$.</p>

<p>(A concise version of the proof: $\mathbf{P} \subseteq \mathbf{L}/\text{poly} \implies \mathbf{P}/\text{poly} \subseteq (\mathbf{L}/\text{poly})/\text{poly} = \mathbf{L}/\text{poly}$.)</p>

CC BY-SA 3.0
2018-01-18T04:41:22.350Z
Awesome!  Thank you very much.  I really appreciate it.  :)
Michael Wehar
CC BY-SA 3.0
2018-01-18T04:26:23.803Z
2018-01-18T17:17:37.307Z
2018-01-18T17:17:37.307Z
William Hoza
<p>A language is in $L/poly$ if there exists a logspace Turing machine that decides the language with polynomial amount of advice.</p>

<p>See here for more info: <a href="https://en.wikipedia.org/wiki/L/poly" rel="noreferrer">https://en.wikipedia.org/wiki/L/poly</a></p>

<blockquote>
  <p><strong>Question</strong></p>
  
  <p>What are the consequences of $P \subseteq L/poly$?</p>
</blockquote>

CC BY-SA 3.0
2018-01-17T22:28:19.633Z
Note: L/poly is also characterized as the class of languages that have polynomial size branching programs.
Michael Wehar
CC BY-SA 3.0
2018-01-17T23:29:46.250Z
Are any interesting consequences of L = P known? (Interesting meaning that (a) a nontrivial proof is required and (b) the consequence is not simply that P would have such-and-such property that L unconditionally has)
William Hoza
CC BY-SA 3.0
2018-01-18T03:47:34.040Z
In my question, I'm open to any consequences that users find meaningful to them even if they are trivial.  A few prospective consequences that I was wondering about were if $P \subseteq L/poly$ implies maybe $P = L$ or $P/poly = L/poly$ or something else weaker related to this.  :)
Michael Wehar
CC BY-SA 3.0
2018-01-18T04:15:15.033Z
@WilliamHoza In regards to your question, I'm not sure if this meets your requirements, but it's my best attempt that I can think of right now: $P = L$ implies both $XP = XL$ and $AP = APSPACE$.  The $XP = XL$ implication would lead to some interesting parameterized lower bounds for $XL$-complete problems as well as kernalization lower bounds.
Michael Wehar
CC BY-SA 3.0
2018-01-18T04:27:01.747Z
Fair enough! $P/poly = L/poly$ is indeed a consequence; see my answer for the proof.
William Hoza
CC BY-SA 3.0
2018-01-18T04:38:45.197Z
@WilliamHoza Also, I think $P = L$ implies $DTIME(t(n)) \neq NTIME(t(n))$ for certain functions $t(n)$.  See "On Separators, Segregators and Time versus Space" for more info.
Michael Wehar
<cc.complexity-theory><circuit-complexity><polynomial-time><advice-and-nonuniformity><logspace>
What are the consequences of $P \subseteq L/poly$?
Michael Wehar
# What are the consequences of $P \subseteq L/poly$?

(Asked by: username_0 on 2018-01-16)

A language is in $L/poly$ if there exists a logspace Turing machine that decides the language with polynomial amount of advice.

See here for more info: <https://en.wikipedia.org/wiki/L/poly>

> **Question**
>
> What are the consequences of $P \subseteq L/poly$?

**Tags:** cc.complexity-theory, circuit-complexity, polynomial-time, advice-and-nonuniformity, logspace
> **Comments:**
> **username_0**: Note: L/poly is also characterized as the class of languages that have polynomial size branching programs.  
> **username_1**: Are any interesting consequences of L = P known? (Interesting meaning that (a) a nontrivial proof is required and (b) the consequence is not simply that P would have such-and-such property that L unconditionally has)  
> **username_0**: In my question, I'm open to any consequences that users find meaningful to them even if they are trivial.  A few prospective consequences that I was wondering about were if $P \subseteq L/poly$ implies maybe $P = L$ or $P/poly = L/poly$ or something else weaker related to this.  :)  
> **username_0**: @WilliamHoza In regards to your question, I'm not sure if this meets your requirements, but it's my best attempt that I can think of right now: $P = L$ implies both $XP = XL$ and $AP = APSPACE$.  The $XP = XL$ implication would lead to some interesting parameterized lower bounds for $XL$-complete problems as well as kernalization lower bounds.  
> **username_1**: Fair enough! $P/poly = L/poly$ is indeed a consequence; see my answer for the proof.  
> **username_0**: @WilliamHoza Also, I think $P = L$ implies $DTIME(t(n)) \neq NTIME(t(n))$ for certain functions $t(n)$.  See "On Separators, Segregators and Time versus Space" for more info.  

---

## 1 answers

### Answer by username_1 on 2018-01-18. Score: 9 | Accepted answer

One simple consequence is $\mathbf{P}/\text{poly} = \mathbf{L}/\text{poly}$. Proof: For any language $A \in \mathbf{P}/\text{poly}$, there is a language $B \in \mathbf{P}$ and a sequence of polynomial-length advice strings $y\_1, y\_2, y\_3, \dots$ such that $x \in A \iff (x, y\_{|x|}) \in B$. By assumption, there is a language $C \in \mathbf{L}$ and a sequence of polynomial-length advice strings $z\_1, z\_2, z\_3, \dots$ such that $(x, y) \in B \iff (x, y, z\_{|(x, y)|}) \in C$. This implies $A \in \mathbf{L}/\text{poly}$; the advice string for $x$ is $(y\_{|x|}, z\_{|(x, y\_{|x|})|})$.

(A concise version of the proof: $\mathbf{P} \subseteq \mathbf{L}/\text{poly} \implies \mathbf{P}/\text{poly} \subseteq (\mathbf{L}/\text{poly})/\text{poly} = \mathbf{L}/\text{poly}$.)

> **Comments:**
> **username_0**: Awesome!  Thank you very much.  I really appreciate it.  :)  

---

