Sur

9

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 \ mathcal L ^ 2 \ subseteq \ mathcal P ? 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.NLNLPNPLL 2 LP L 2P L 2P L 2PNLL2LL2LPL2PL2PL2P

De plus, qu'il existe ou non un problème NP qui n'est pas NP complet est une question ouverte, et une telle existence impliquerait LNP , comme chaque L problème est complet pour L . Mais ne savons-nous vraiment pas que LNP ? 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 L2P et LNP .

Leandro Zatesko
la source
3
J'ai posé un sous-ensemble de cette question: cstheory.stackexchange.com/q/14159/4193
argentpepper
2
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? N E x p T i m e L 2PTC0NExpTimeL2P
Kaveh
3
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.LPL
Kaveh
4
@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. P # P T C 0 N P T C 0TC0P#PTC0NPTC0
Ryan Williams
@Ryan, vous avez raison, je pensais à non uniforme , ce qui importe ici, c'est la version uniforme comme vous l'avez écrit. TC0
Kaveh

Réponses:

12

Vous pouvez vérifier le papier suivant:

Lemmes translationnels, temps polynomial et -space(logn)j par Ronald V. Book (1976).

Les figures 1 et 2 du document résument ce qui est connu et ce qui est inconnu.

J'ai mis le théorème 3.10 dans le document ici:

  • DTIME(poly(n))DSPACE(poly(logn)) ;
  • pour chaque , ;D T I M E ( n j ) D S P A C E ( p o l y ( log n ) )j1DTIME(nj)DSPACE(poly(logn))
  • pour chaque , .D T I M E ( n j ) D S P A C E ( ( log n ) k )j,k1DTIME(nj)DSPACE((logn)k)
Abuzer Yakaryilmaz
la source
3
Une copie en ligne gratuite est ici .
Kaveh