Sur

Nous savons que . D'après le théorème de Savitch, , et, depuis Space Hierarchy Teorem, . Donc, comme nous ne savons pas si , nous ne savons pas si , ou savons-nous que ? Quelqu'un at-il essayé de prouver que ? Quels sont les derniers résultats ou efforts en ce sens? J'ai essayé d'écrire une enquête sur ce sujet, mais je n'ai rien trouvé de pertinent. $\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}$ $\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$

De plus, qu'il existe ou non un problème $\mathcal{N\!P}$ qui n'est pas $\mathcal{N\!P}$ complet est une question ouverte, et une telle existence impliquerait $\mathcal L\neq\mathcal{N\!P}$ , comme chaque $\mathcal L$ problème est complet pour $\mathcal L$ . Mais ne savons-nous vraiment pas que $\mathcal L\neq\mathcal{N\!P}$ ? Quelqu'un a-t-il essayé de le prouver? Encore une fois, quels sont les derniers résultats ou efforts en ce sens?

Peut-être que je manque quelque chose ou que je cherche mal, mais je n'ai trouvé personne travaillant sur les questions $\mathcal L^2\subseteq \mathcal P$ et $\mathcal L\neq\mathcal{N\!P}$ .

reference-request complexity-classes open-problem hierarchy-theorems Leandro Zatesko
la source

J'ai posé un sous-ensemble de cette question: cstheory.stackexchange.com/q/14159/4193

argentpepper

Nous ne connaissons aucune séparation entre et . Donc, tout confinement strict entre les classes entre elles est inconnu. Est-ce plus @ argentpepper Quelles sont les conséquences de ? question répondre à vos questions?

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 et ses collègues ont travaillé sur une approche pour séparer de . Je pense que ce qui suit est leur plus récent travail publié à ce sujet: Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam, "Pebbles and Branching Programs for Tree Evaluation" , 2012.

P

$\mathsf{P}$

L

$\mathsf{L}$

Kaveh

@Kaveh Nous savons certainement que UNIFORM est différent de - cf. Limites inférieures du circuit d'Allender pour le permanent. (Uniform est la version qui est pertinente pour la présente discussion.) Mais oui, même la séparation de de l'uniforme - est ouverte.

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, vous avez raison, je pensais à non uniforme , ce qui importe ici, c'est la version uniforme comme vous l'avez écrit.

T C^{0}

$\mathsf{TC^0}$

Kaveh

Sur

Réponses: