Was sind die Konsequenzen von

14

Eine Sprache ist in , wenn es eine logspace Turingmaschine vorhanden ist , der die Sprache mit Polynom Menge Rat entscheidet.L/poly

Weitere Informationen finden Sie hier: https://en.wikipedia.org/wiki/L/poly

Frage

Was sind die Konsequenzen von ?PL/poly

Michael Wehar
quelle
Anmerkung: L / poly wird auch als die Klasse von Sprachen charakterisiert, die Verzweigungsprogramme für polynomielle Größen haben.
Michael Wehar
1
Sind interessante Konsequenzen von L = P bekannt? (Interessant bedeutet, dass (a) ein nichttrivialer Beweis erforderlich ist und (b) die Konsequenz nicht einfach ist, dass P die und die Eigenschaft haben würde, die L unbedingt hat)
William Hoza
In meiner Frage bin ich offen für alle Konsequenzen, die Benutzer für sinnvoll halten, auch wenn sie unbedeutend sind. Einige potenziellen Folgen , die ich frage mich , waren etwa wenn vielleicht bedeutet P = L oder P / p o l y = L / p o l y oder etwas anderes schwächer in Bezug auf diese. :)PL/polyP=LP/poly=L/poly
Michael Wehar
1
Meinetwegen! ist in der Tat eine Konsequenz; Siehe meine Antwort für den Beweis. P/poly=L/poly
William Hoza
1
Auch @WilliamHoza, ich denke , bedeutet , D T I M E ( t ( n ) ) N T I M E ( t ( n ) ) für bestimmte Funktionen t ( n ) . Weitere Informationen finden Sie unter "Trennzeichen, Trennzeichen und Zeit gegen Raum". P=LDTIME(t(n))NTIME(t(n))t(n)
Michael Wehar

Antworten:

9

Eine einfache Folge ist . Beweis: Für jede Sprache A P / poly gibt es eine Sprache B P und eine Folge von polynomlangen Hinweiszeichenfolgen y 1 , y 2 , y 3 , …, so dass x AP/poly=L/polyAP/polyBPy1,y2,y3, . Unter der Annahme gibt es eine Sprache C L und eine Folge von polynomlangen Hinweiszeichenfolgen z 1 , z 2 , z 3 , …, so dass ( x , y ) BxA(x,y|x|)BCLz1,z2,z3, . Dies impliziert A L / poly ; die Hinweiszeichenfolge für x ist ( y | x | , z | ( x , y | x | ) | ) .(x,y)B(x,y,z|(x,y)|)CAL/polyx(y|x|,z|(x,y|x|)|)

(Eine knappe Version des Beweises: )PL/polyP/poly(L/poly)/poly=L/poly

William Hoza
quelle
Genial! Vielen Dank. Ich weiß das wirklich zu schätzen. :)
Michael Wehar