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.
Voir ici pour plus d'informations: https://en.wikipedia.org/wiki/L/poly
Question
Quelles sont les conséquences de ?
cc.complexity-theory
circuit-complexity
polynomial-time
advice-and-nonuniformity
logspace
Michael Wehar
la source
la source
Réponses:
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 ∈P/poly=L/poly A∈P/poly B∈P y1,y2,y3,… . 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 ) ∈ Bx∈A⟺(x,y|x|)∈B C∈L z1,z2,z3,… (x,y)∈B⟺(x,y,z|(x,y)|)∈C A∈L/poly x (y|x|,z|(x,y|x|)|)
la source