¿Cuáles son las consecuencias de

Un idioma está en si existe un espacio de registro de la máquina de Turing que decide el idioma con una cantidad polinómica de consejos.$L/poly$

Consulte aquí para obtener más información: https://en.wikipedia.org/wiki/L/poly

Pregunta

¿Cuáles son las consecuencias de ?$P \subseteq L/poly$

Una consecuencia simple es . Prueba: para cualquier lenguaje A ∈ P / poly , hay un lenguaje B ∈ P y una secuencia de cadenas de consejos de longitud polinómica y 1 , y 2 , y 3 , ... de modo 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$ . Por supuesto, hay un lenguaje C ∈ L y una secuencia de cadenas de consejos de longitud polinómica z 1 , z 2 , z 3 , ... tal que ( x , y ) ∈ $x \in A \iff (x, y_{|x|}) \in B$$C \in \mathbf{L}$$z_1, z_2, z_3, \dots$ . Esto implica A ∈ L / poli ; la cadena de consejos para x es ( y | x | , z | ( x , y | x | ) | ) .$(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|})|})$

(Una versión concisa de la prueba: .)$\mathbf{P} \subseteq \mathbf{L}/\text{poly} \implies \mathbf{P}/\text{poly} \subseteq (\mathbf{L}/\text{poly})/\text{poly} = \mathbf{L}/\text{poly}$