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$?
$\begingroup$
$\endgroup$
6
asked Jan 16, 2018 at 7:50
-
$\begingroup$ Note: L/poly is also characterized as the class of languages that have polynomial size branching programs. $\endgroup$– Michael WeharJan 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$– William HozaJan 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$– Michael WeharJan 18, 2018 at 3:47
-
1$\begingroup$ Fair enough! $P/poly = L/poly$ is indeed a consequence; see my answer for the proof. $\endgroup$– William HozaJan 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$– Michael WeharJan 18, 2018 at 4:38
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
1
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, 2018 at 4:41