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.

— 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

Możesz sprawdzić następujący papier:

Lematy translacyjne, czas wielomianowy i $(\log n)^j$ -space autorstwa Ronalda V. Booka (1976).

Ryciny 1 i 2 w artykule przedstawiają podsumowanie tego, co jest znane, a co nieznane.

W tekście umieściłem Twierdzenie 3.10:

$DTIME(poly(n)) \neq DSPACE(poly(\log n))$ ;
dla każdego $j \geq 1$ , $DTIME(n^j) \neq DSPACE(poly(\log n))$ ;
dla każdego $j,k \geq 1$ , $DTIME(n^j) \neq DSPACE( (\log n)^k )$ .

— Abuzer Yakaryilmaz
źródło

Bezpłatna kopia online jest tutaj .

— Kaveh