Quelles sont les conséquences de

14

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 ?PL/poly

Michael Wehar
la source
Remarque: L / poly est également caractérisé comme la classe de langues qui ont des programmes de ramification de taille polynomiale.
Michael Wehar
1
Des conséquences intéressantes de L = P sont-elles connues? (Signifiant intéressant que (a) une preuve non triviale est requise et (b) la conséquence n'est pas simplement que P aurait telle ou telle propriété que L a inconditionnellement)
William Hoza
Dans ma question, je suis ouvert à toutes les conséquences que les utilisateurs trouvent significatives pour eux, même si elles sont triviales. Quelques conséquences prospectives que je me demandais étaient si implique peut-être P = L ou P / p o l y = L / p o l y ou quelque chose d'autre plus faible lié à cela. :)PL/polyP=LP/poly=L/poly
Michael Wehar
1
C'est suffisant! est en effet une conséquence; voir ma réponse pour la preuve. P/poly=L/poly
William Hoza
1
@WilliamHoza Aussi, je pense que implique D T I M E ( t ( n ) ) N T I M E ( t ( n ) ) pour certaines fonctions t ( n ) . Voir «Sur les séparateurs, les séparateurs et le temps par rapport à l'espace» pour plus d'informations. P=LDTIME(t(n))NTIME(t(n))t(n)
Michael Wehar

Réponses:

9

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/polyAP/polyBPy1,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 ) BxA(x,y|x|)BCLz1,z2,z3,(x,y)B(x,y,z|(x,y)|)CAL/polyx(y|x|,z|(x,y|x|)|)

PL/polyP/poly(L/poly)/poly=L/poly.)

William Hoza
la source
Awesome! Thank you very much. I really appreciate it. :)
Michael Wehar