Y a-t-il une justification pour croire que

Tout d' abord, permettez - moi de citer le scepticisme que . Comme il a été démontré que la connectivité du graphe non orienté est dans (Reingold), et que (Immerman-Szelepcsényi), je pense que la confiance dans n'a que diminué. Certains chercheurs éminents n'ont jamais eu une forte conviction. Par exemple, Juris Hartmanis (fondatrice du département CS de Cornell et lauréate du prix Turing) a déclaré: $L \neq NL$ $L$ $NL=coNL$ $L \neq NL$

Nous pensons que NLOGSPACE diffère de LOGSPACE, mais pas avec la même profondeur de conviction que pour les autres classes de complexité. (La source)

Je sais qu'il a dit des choses similaires dans la littérature dès les années 70.

Il existe des preuves contre , bien qu'elles soient circonstancielles. Il y a eu des travaux sur la preuve des limites inférieures d' espace pour - connectivité (canonique problème -complete) dans les modèles de calcul restreints. Ces modèles sont assez forts pour exécuter l'algorithme du théorème de Savitch (qui donne un algorithme d'espace ) mais ne sont pas suffisamment forts pour faire mieux asymptotiquement. Voir le document "Limites inférieures étroites pour la connectivité st sur le modèle NNJAG" $L=NL$ $s$ $t$ $NL$ $O(\log^2 n)$ . Ces bornes inférieures NNJAG montrent que, s'il est possible de battre le théorème de Savitch et même d'obtenir , il faudra certainement trouver un algorithme très différent de Savitch. $NL \subseteq SPACE[o(\log^2 n)]$

Pourtant, je ne connais pas de conséquences formelles improbables et inattendues qui viennent de (à l'exception des conséquences évidentes). Encore une fois, cela est principalement parce que nous savons déjà des choses comme . $L=NL$ $NL=coNL$

Ryan Williams
la source

Ryan, les modèles dans lesquels vous pouvez prouver la borne inférieure

peuvent-ils faire une connectivité non dirigée dans l' espace

? S'il s'agit de modèles non uniformes, je suppose qu'il devrait être simple d'implémenter un algorithme basé sur des séquences de traversées universelles, même dans un modèle très restreint

Ω (\log^{2} n)

$\Omega(\log^2 n)$

O (\log n)

$O(\log n)$

Luca Trevisan

@Luca, l'article cité par Ryan par Edmonds et al. note que la connectivité non dirigée peut être résolue dans l' espace

et le temps polynomial par un algorithme randomisé utilisant des séquences de traversées universelles. Je soupçonne qu'il peut être dérandomisé "à la" Reingold tout en restant à l'intérieur du modèle NNJAG, mais je n'ai pas vérifié.

O (\log n)

$O(\log n)$

arnab

Je pense que le modèle peut faire une connectivité non dirigée sur des graphiques réguliers dans l' espace

. La page 4 donne une description du modèle. On nous permet de

cailloux se déplacer sur les nœuds du graphe (pour nous, soit

"états", et une fonction de transition qui prend un état et un index de nœud caillouteux, et sort l'index d'une arête pour déplacer le caillou. (Les arêtes d'un sommet

sont indexées

.) En utilisant

O (\log n)

$O(\log n)$

p

$p$

p = 1

$p=1$

q

$q$

v

$v$

0, \dots, d

$0,\ldots,d$

q = n^{O (1)}

$q=n^{O(1)}$ états, nous pouvons coder une séquence de traversée universelle. L'utilisation d'espace d'un NNJAG est définie comme étant

qui dans ce cas est

p \log n + \log q

$p \log n + \log q$

O (\log n)

$O(\log n)$

Ryan Williams

Y a-t-il une justification pour croire que

Réponses: