Jakie są konsekwencje

14

Język jest w języku jeśli istnieje maszyna Turinga z logami, która decyduje o języku z wielomianową ilością porad.L/poly

Zobacz tutaj, aby uzyskać więcej informacji: https://en.wikipedia.org/wiki/L/poly

Pytanie

Jakie są konsekwencje ?PL/poly

Michael Wehar
źródło
Uwaga: L / poly jest również scharakteryzowany jako klasa języków, które mają programy do rozgałęziania wielomianów.
Michael Wehar
1
Czy znane są jakieś interesujące konsekwencje L = P? (Interesujące, co oznacza, że ​​(a) wymagany jest nietrywialny dowód i (b) konsekwencją nie jest po prostu to, że P miałby taką a taką właściwość, jaką L bezwarunkowo ma)
William Hoza
W moim pytaniu jestem otwarty na wszelkie konsekwencje, które użytkownicy uznają za znaczące, nawet jeśli są trywialne. Zastanawiałem się nad kilkoma potencjalnymi konsekwencjami, jeśli implikuje P = L lub P / p o l y = L / p o l y lub coś innego słabszego z tym związanego. :)PL/polyP=LP/poly=L/poly
Michael Wehar
1
Słusznie! jest rzeczywiście konsekwencją; zobacz moją odpowiedź na dowód. P/poly=L/poly
William Hoza
1
@WilliamHoza Również myślę, że oznacza D T I M E ( t ( n ) ) N T I M E ( t ( n ) ) dla niektórych funkcji t ( n ) . Aby uzyskać więcej informacji, zobacz „Separatory, segregatory i czas a przestrzeń”. P=LDTIME(t(n))NTIME(t(n))t(n)
Michael Wehar,

Odpowiedzi:

9

Jedną z prostych konsekwencji jest . Dowód: dla dowolnego języka A P / poli istnieje język B P i sekwencja ciągów porad wielomianowych y 1 , y 2 , y 3 , takich, że x AP/poly=L/polyAP/polyBPy1,y2,y3, . Z założenia istnieje język C L i sekwencja ciągów porad wielomianowych z 1 , z 2 , z 3 , takich, że ( x , y ) BxA(x,y|x|)BCLz1,z2,z3, . To implikuje A L / poli ; ciąg porady dla x to ( y | x | , z | ( x , y | x | ) | ) .(x,y)B(x,y,z|(x,y)|)CAL/polyx(y|x|,z|(x,y|x|)|)

(Zwięzła wersja dowodu: PL/polyP/poly(L/poly)/poly=L/poly

William Hoza
źródło
Niesamowite! Dziękuję Ci bardzo. Bardzo to doceniam. :)
Michael Wehar