Jakie są konsekwencje

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 ? $P \subseteq L/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

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

lub

lub coś innego słabszego z tym związanego. :)

P \subseteq L / p o l y

$P \subseteq L/poly$

P = L

$P = L$

P / p o l y = L / p o l y

$P/poly = L/poly$

— Michael Wehar

Słusznie!

jest rzeczywiście konsekwencją; zobacz moją odpowiedź na dowód.

P / p o l y = L / p o l y

$P/poly = L/poly$

— William Hoza

@WilliamHoza Również myślę, że

oznacza

dla niektórych funkcji

. Aby uzyskać więcej informacji, zobacz „Separatory, segregatory i czas a przestrzeń”.

P = L

$P = L$

D T I M E (t (n)) \neq N T I M E (t (n))

$DTIME(t(n)) \neq NTIME(t(n))$

t (n)

$t(n)$

— Michael Wehar,

Jedną z prostych konsekwencji jest . Dowód: dla dowolnego języka istnieje język i sekwencja ciągów porad wielomianowych takich, że $\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$ . Z założenia istnieje język i sekwencja ciągów porad wielomianowych takich, że $x \in A \iff (x, y_{|x|}) \in B$ $C \in \mathbf{L}$ $z_1, z_2, z_3, \dots$ . To implikuje ; ciąg porady dla to . $(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|})|})$

(Zwięzła wersja dowodu: $\mathbf{P} \subseteq \mathbf{L}/\text{poly} \implies \mathbf{P}/\text{poly} \subseteq (\mathbf{L}/\text{poly})/\text{poly} = \mathbf{L}/\text{poly}$

— William Hoza
źródło

Niesamowite! Dziękuję Ci bardzo. Bardzo to doceniam. :)

— Michael Wehar