Quelles sont les conséquences de

Une langue est en s'il existe une machine de Turing de l'espace de log qui décide de la langue avec une quantité polynomiale de conseils.$L/poly$

Voir ici pour plus d'informations: https://en.wikipedia.org/wiki/L/poly

Question

Quelles sont les conséquences de ?$P \subseteq L/poly$

Une conséquence simple est . Preuve: Pour tout langage A ∈ P / poly , il existe un langage B ∈ P et une séquence de chaînes de conseil de longueur polynomiale y 1 , y 2 , y 3 , … telles que x $\mathbf{P}/\text{poly} = \mathbf{L}/\text{poly}$$A \in \mathbf{P}/\text{poly}$$B \in \mathbf{P}$$y_1, y_2, y_3, \dots$ . Par hypothèse, il existe un langage C ∈ L et une séquence de chaînes de conseil de longueur polynomiale z 1 , z 2 , z 3 , … telles que ( x , y ) ∈ $x \in A \iff (x, y_{|x|}) \in B$$C \in \mathbf{L}$$z_1, z_2, z_3, \dots$$(x, y) \in B \iff (x, y, z_{|(x, y)|}) \in C$$A \in \mathbf{L}/\text{poly}$$x$$(y_{|x|}, z_{|(x, y_{|x|})|})$

$\mathbf{P} \subseteq \mathbf{L}/\text{poly} \implies \mathbf{P}/\text{poly} \subseteq (\mathbf{L}/\text{poly})/\text{poly} = \mathbf{L}/\text{poly}$.)