14
$\begingroup$

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$?

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

1 Answer 1

9
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.