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


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

  • $\begingroup$ Note: L/poly is also characterized as the class of languages that have polynomial size branching programs. $\endgroup$ Jan 17 '18 at 22:28
  • 1
    $\begingroup$ 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) $\endgroup$ Jan 17 '18 at 23:29
  • $\begingroup$ 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. :) $\endgroup$ Jan 18 '18 at 3:47
  • 1
    $\begingroup$ Fair enough! $P/poly = L/poly$ is indeed a consequence; see my answer for the proof. $\endgroup$ Jan 18 '18 at 4:27
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 18 '18 at 4:38

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

  • $\begingroup$ Awesome! Thank you very much. I really appreciate it. :) $\endgroup$ Jan 18 '18 at 4:41

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.