Na

Wiemy to $\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}$ . Z twierdzenia Savitcha $\mathcal{N\!L}\subseteq\mathcal{L}^2$ , a od Space Hierarchy Teorem, $\mathcal{L}\neq\mathcal{L}^2$ . Ponieważ nie wiemy, czy $\mathcal L\neq\mathcal P$ nie wiemy czy $\mathcal L^2\subseteq\mathcal P$ czy wiemy o tym $\mathcal L^2\not\subseteq\mathcal P$ ? Czy ktoś próbował udowodnić, że ? Jakie są najnowsze wyniki lub wysiłki w ten sposób? Próbowałem napisać ankietę na ten temat, ale nie znalazłem nic istotnego. $\mathcal L^2\subseteq\mathcal P$

Ponadto, czy istnieje problem który nie jest -kompletny, jest pytaniem otwartym, a takie istnienie oznaczałoby , jak co problemu jest zakończone dla . Ale czy tak naprawdę nie wiemy, że ? Czy ktoś próbował to udowodnić? Ponownie, jakie są najnowsze wyniki lub wysiłki w ten sposób? $\mathcal{N\!P}$ $\mathcal{N\!P}$ $\mathcal L\neq\mathcal{N\!P}$ $\mathcal L$ $\mathcal L$ $\mathcal L\neq\mathcal{N\!P}$

Może coś brakuje lub źle wyszukuję, ale nie mogłem znaleźć nikogo, kto pracowałby na $\mathcal L^2\subseteq \mathcal P$ i $\mathcal L\neq\mathcal{N\!P}$ pytania.

reference-request complexity-classes open-problem hierarchy-theorems Leandro Zatesko
źródło

Zadałem podzbiór tego pytania: cstheory.stackexchange.com/q/14159/4193

argentpepper

Nie wiemy między nimi żadnej separacji

T C^{0}

$\mathsf{TC^0}$ i

N E x p T i m e

$\mathsf{NExpTime}$ . Tak więc jakiekolwiek ścisłe ograniczenie między klasami jest nieznane. Czy to plus @ argentpepper Jakie są konsekwencje

L^{2} \subseteq P

$\mathsf{L}^2 \subseteq \mathsf{P}$ ? pytanie odpowiedzieć na twoje pytania?

Kaveh

Steve Cook wraz z kolegami pracował nad podejściem do separacji

P

$\mathsf{P}$ od

L

$\mathsf{L}$ . Wydaje mi się, że ich najnowszą opublikowaną pracą są: Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam, „Kamyki i programy rozgałęziające do oceny drzew” , 2012.

Kaveh

@Kaveh Z pewnością wiemy, że UNIFORM

T C^{0}

$TC^0$ jest różny od

P^{# P}

$P^{\#P}$ - por. Obwód Allendera w dolnej granicy dla Stałego. (Mundur

T C^{0}

$TC^0$ jest wersją, która jest istotna dla niniejszej dyskusji.) Ale tak, nawet oddzielenie

N P

$NP$ z munduru

T C^{0}

$TC^0$ jest otwarte.

Ryan Williams

@ Ryan, masz rację, myślałem o niejednolitości

T C^{0}

$\mathsf{TC^0}$ , liczy się tutaj jednolita wersja, jak napisałeś.

Kaveh

Na

Odpowiedzi: