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$ – Michael Wehar 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$ – William Hoza 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$ – Michael Wehar 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$ – William Hoza 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$ – Michael Wehar 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$ – Michael Wehar 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.