Quelles sont les conséquences de

46

On sait que LNLP et LNLL2 polyL , où L2=DSPACE(log2n) . Nous savons aussi que polyLPparce que ce dernier a des problèmes complets dans les réductions logarithmiques d’espaces multiples, alors que ce n’est pas le cas (en raison du théorème de la hiérarchie spatiale). Afin de mieux comprendre la relation entre polyL et P , il peut être utile de comprendre d'abord la relation entre L2 et P .

Quelles sont les conséquences de L2P ?

Qu'en est- il le plus fort LkP pour k>2 , ou plus faible L1+ϵP pour ϵ>0 ?

argentpepper
la source
4
@OrMeir J'ai récemment ajouté une explication de ce fait à l'article de Wikipedia sur polyL .
argentpepper
13
L2PLPLL2
12
Neat question! Je pense que ça vaut vraiment une prime. Btw, voici une observation simple, si L2P , alors DSPACE(n)DTIME(2O(n)) . Nous avons donc un algorithme plus efficace pour CNF-SAT et nous réfutons ETH (hypothèse de temps exponentiel).
Michael Wehar
3
Suivant le commentaire de @ MichaelWehar, l’ argument résulte d’un argument de remplissage standard qui s’étend aux hypothèses les plus faibles: si L1+ϵ est dans P , alors tout problème pouvant être résolu en espace linéaire (y compris le problème de satisfiabilité) peut être résolu. être résolu dans le temps 2O(n11+ϵ) .
argentpepper
3
@SajinKoroth: Je pense que votre commentaire, ainsi que celui de Michael Wehar (et du suivi de argentpepper) devraient être des réponses ...
Joshua Grochow

Réponses:

26

La conséquence suivante est évidente: impliquerait et donc .L P L PL1+ϵPLPLP

Selon le théorème de la hiérarchie de l'espace, . Si alors .L 1 + εP LL 1 + εPϵ>0:LL1+ϵL1+ϵPLL1+ϵP

Sajin Koroth
la source
Petite note: Si , nous avons ou . P N L N L LPLPNLNLL
Michael Wehar
27

L2P réfuterait l' hypothèse du temps exponentiel .

Si un argument de remplissage . Cela signifie que le problème de satisfiabilité peut être résolu en étapes, ce qui réfute l'hypothèse du temps exponentiel.L2P DSPACE(n)DTIME(2O(n))SATDSPACE(n)2o(n)

Plus généralement, pour implique .DSPACE(logkn)Pk1SATDSPACE(n)DTIME(2O(n1k))

(Cette réponse est développée à partir d'un commentaire de @MichaelWehar.)

argentpepper
la source
Merci d'avoir développé le commentaire! Je vous en suis reconnaissant. :)
Michael Wehar
1
De plus, la dernière hypothèse implique également que est dans DSPACE ( ) DTIME ( ). QBFn2O(n1k)
Michael Wehar
8

L'isomorphisme de groupe (avec les groupes donnés sous forme de tables de multiplication) serait dans P. Lipton, Snyder et Zalcstein a montré que ce problème est dans , mais il est toujours possible de savoir s'il est dans P. La meilleure limite supérieure actuelle est -time, et comme il se réduit à un isomorphisme de graphe, il constitue un obstacle important à la mise en iso de graphes dans P.L2nO(logn)

Je me demande à quels autres problèmes naturels et importants cela pourrait s’appliquer: c’est-à-dire, en mais avec leur meilleur temps connu quasi-polynomial.L2

Joshua Grochow
la source
1
Plus spécifiquement, le problème plus général de l'isomorphisme de quasigroupe est dans , qui est une sous-classe de . β2FOLLL2
argentpepper
1
De plus, le problème de rang de groupe (étant donné un groupe fini G sous forme de table de multiplication et un entier k , G a-t-il un ensemble générateur de cardinalité k ?) A également cette propriété. L'algorithme est juste une recherche sur les sous-ensembles de G de la cardinalité k, mais utilise deux faits importants: (1) chaque groupe fini a un ensemble générateur de taille logarithmique et (2) l'appartenance à un sous-groupe est dans , ce qui est égal à . SLL
argentpepper
1

Revendication: Si pour certains , alors et .LkPk>2Plog(CFL)PNL

Supposons que pour certains .LkPk>2

D'après " Limites de la mémoire pour la reconnaissance des langages sans contexte et sensibles au contexte ", nous savons que . D'après le théorème de la hiérarchie de l'espace, nous savons que .CFLDSPACE(log2(n))DSPACE(log2(n))DSPACE(logk(n))

Par conséquent, nous obtenons .log(CFL)DSPACE(log2(n))DSPACE(logk(n))P

Aussi, par le théorème de Savitch, nous savons que . Par conséquent, nous obtenons .NLL2NLDSPACE(log2(n))DSPACE(logk(n))P

Michael Wehar
la source