Auf

Wir wissen, dass $\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}$ . Aus Savitchs Theorem, $\mathcal{N\!L}\subseteq\mathcal{L}^2$ $\mathcal{L}\neq\mathcal{L}^2$ $\mathcal L\neq\mathcal P$ $\mathcal L^2\subseteq\mathcal P$ $\mathcal L^2\not\subseteq\mathcal P$ $\mathcal L^2\subseteq\mathcal P$

Darüber hinaus ist es eine offene Frage , ob ein -Problem vorliegt oder nicht, das nicht -vollständig ist, und eine solche Existenz würde , da jedes Problem für . Aber wissen wir wirklich nicht, dass ? Hat jemand versucht, dies zu beweisen? Was sind die neuesten Ergebnisse oder Bemühungen auf diese Weise? $\mathcal{N\!P}$ $\mathcal{N\!P}$ $\mathcal L\neq\mathcal{N\!P}$ $\mathcal L$ $\mathcal L$ $\mathcal L\neq\mathcal{N\!P}$

Vielleicht fehlt mir etwas oder ich suche falsch, aber ich konnte niemanden finden, der an den Fragen und . $\mathcal L^2\subseteq \mathcal P$ $\mathcal L\neq\mathcal{N\!P}$

reference-request complexity-classes open-problem hierarchy-theorems Leandro Zatesko
quelle

Ich habe eine Teilmenge dieser Frage gestellt: cstheory.stackexchange.com/q/14159/4193

argentpepper

Wir kennen keine Trennung zwischen und . Eine strikte Eingrenzung zwischen Klassen zwischen ihnen ist daher unbekannt. Ist dies plus @ argentpeppers Was sind die Konsequenzen von ? Frage Beantworten Sie Ihre Fragen?

T C^{0}

$\mathsf{TC^0}$

N E x p T i m e

$\mathsf{NExpTime}$

L^{2} \subseteq P

$\mathsf{L}^2 \subseteq \mathsf{P}$

Kaveh

Steve Cook hat mit seinen Kollegen an einem Ansatz gearbeitet, um von zu trennen . Ich denke, das Folgende ist ihre jüngste veröffentlichte Arbeit dazu: Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam, "Kiesel- und Verzweigungsprogramme für die Baumbewertung" , 2012.

P

$\mathsf{P}$

L

$\mathsf{L}$

Kaveh

@Kaveh Wir wissen sicherlich, dass UNIFORM sich von - vgl. Allender's Circuit Untergrenzen für den Permanent. (Uniform ist die Version, die für die vorliegende Diskussion relevant ist.) Aber ja, sogar die Trennung von und Uniform- ist offen.

T C^{0}

$TC^0$

P^{# P}

$P^{\#P}$

T C^{0}

$TC^0$

N P

$NP$

T C^{0}

$TC^0$

Ryan Williams

@ Ryan, du hast recht, ich dachte an ungleichmäßige , was hier zählt, ist die einheitliche Version, wie du geschrieben hast.

T C^{0}

$\mathsf{TC^0}$

Kaveh

Auf

Antworten: