Comment prouver que USTCONN nécessite un espace logarithmique?

USTCONN est le problème qui nécessite de décider s'il existe un chemin entre le sommet source et le sommet cible t dans un graphique G , où ils sont tous donnés dans le cadre de l'entrée.$s$$t$$G$

Omer Reingold a montré que USTCONN est en L (doi: 10.1145 / 1391289.1391291 ). La preuve construit un expanseur à degré constant au moyen du produit en zigzag. Un extenseur à degré constant a un diamètre logarithmique et on peut alors vérifier tous les chemins possibles en utilisant un nombre constant de marqueurs de taille logarithmique.

Le résultat de Reingold donne une limite supérieure logarithmique sur la complexité spatiale d'USTCONN, résolvant sa complexité spatiale "jusqu'à un facteur constant" selon l'article. Je suis curieux de connaître la borne inférieure correspondante, qui n'est mentionnée nulle part ailleurs dans le document.

Comment prouver que l'espace logarithmique est nécessaire pour décider USTCONN dans le pire des cas?

Modifier: Fixez la représentation d'entrée comme étant la matrice d'adjacence graphe orienté simple symétrique N -vertex sous-jacent , avec les lignes répertoriées consécutivement pour former une chaîne de N 2 bits.$N \times N$$N$$N^2$

Lewis et Papadimitriou ont montré (doi: 10.1016 / 0304-3975 (82) 90058-5 ) que USTCONN est SL-complet, ce qui, avec le résultat de Reingold, implique que SL = L. Savitch a montré (doi: 10.1016 / S0022-0000 (70) 80006-X ) que . DSPACE supplémentaire ( f ( n ) ) = DSPACE ( 1 ) pour toute fonction calculable f ( n ) = o ( log log n $\text{NSPACE}(n) \subseteq \text{DSPACE}(n^2)$$\text{DSPACE}(f(n)) = \text{DSPACE}(1)$$f(n) = o(\log\log n)$par Stearns, Hartmanis et Lewis (doi: 10.1109 / FOCS.1965.11 ), donc un espace d' au moins est nécessaire pour USTCONN. Enfin, les classes habituelles connues pour être inférieures à L (telles que NC 1 ) sont définies en termes de circuits et ne sont évidemment pas comparables à une classe définie en termes de limite d'espace.$\Omega(\log\log n)$$\text{NC}^1$

Pour autant que je puisse voir, cela laisse la possibilité (certes peu probable) qu'il existe un algorithme déterministe encore meilleur qui utilise uniquement l' espace mais Ω ( log log n ) , pour certains δ < 1 , ou même un algorithme non déterministe pour USTCONN que les utilisations o ( ( log n ) une / 2 ) de l' espace.$O((\log n)^\delta)$$\Omega(\log \log n)$$\delta < 1$$o((\log n)^{1/2})$

Selon le théorème de la hiérarchie spatiale , tant que f ( n ) est constructible dans l'espace. Cela pourrait suggérer que USTCONN ne peut pas être dans DSPACE ( o ( log n ) $\text{DSPACE}(o(f(n)) \subsetneq \text{DSPACE}(f(n))$$f(n)$$\text{DSPACE}(o(\log n))$. Cependant, USTCONN étant achevé pour L dans le cadre des réductions d'espace journal ne semble pas impliquer cela. Il semble toujours possible que USTCONN ait une structure suffisante pour encoder tout problème dans L au moyen d'une réduction de l'espace de journalisation, mais USTCONN lui-même ne nécessite qu'un espace sublogarithmique.

Tant qu'il y a un langage dans L qui nécessite un espace logarithmique, alors montrer que USTCONN est complet pour L sous une stricte "plus faible" que la réduction de l'espace de log donnerait la borne inférieure souhaitée.

USTCONN est-il complet pour L sous une réduction qui nécessite un espace ?$o(\log n)$

Immerman a montré (doi: 10.1137 / 0216051 ) qu'une version d'accessibilité dirigée dans laquelle le chemin souhaité (mais pas le graphique lui-même) est déterministe, est complète pour L sous les réductions de premier ordre, qui sont calculables par des circuits AC 0 . Cela pourrait alors être adapté pour montrer que USTCONN est complet pour L sous FO-réductions. Cependant, bien que AC 0 soit strictement contenu dans L, AC 0 est à nouveau une classe de circuit et je ne connais aucun moyen d'effectuer des réductions FO dans l'espace sublogarithmique.$^0$$^0$$^0$

Edit 2015-07-14: C'est une question philosophique intéressante de savoir si l'utilisation de l'espace d'une MT doit inclure la taille d'un index dans l'entrée (permettant ainsi un accès aléatoire à l'entrée, mais nécessitant un bit supplémentaire si l'entrée double de taille ), ou si l'espace utilisé par une MT est le nombre de carrés de bande de travail visités pendant un calcul (ce qui suppose que la tête de bande d'entrée est fixe et ne change pas lorsque la taille de la bande d'entrée double). L'ancienne définition de style RAM donne immédiatement une limite inférieure d'espace de journal pour toutcalcul et modélise les ordinateurs actuels qui gardent une trace de la position actuelle dans un fichier comme décalage par rapport au début du fichier. Cette dernière définition classique suppose une bande semblable à du papier avec une tête de lecture fixe qui ne sait rien de la bande autre que le symbole d'entrée actuel, ce qui est probablement ce que Turing voulait dans son article de 1937.

Des arguments heuristiques comme le commentaire de Thomas, selon lequel il n'est même pas possible d'indexer l'entrée avec bits d'espace, semblent prendre une définition moderne de style RAM. Stearns / Hartmanis / Lewis utilisent la définition de style TM, comme le font la plupart des travaux classiques dans le calcul délimité par l'espace.$o(\log n)$

On peut prouver une limite inférieure d'espace de log pour USTCONN représentée comme une matrice d'adjacence en notant que le langage unaire des carrés parfaits nécessite que l'espace de log reconnaisse (voir Rūsiņš Freivalds, Models of Computation, Riemann Hypothesis, and Classical Mathematics , SOFSEM 1998, LNCS 1521, 89 –106. Doi: 10.1007 / 3-540-49477-4_6 ( préimpression)). Ensuite, la même borne inférieure s'applique à USTCONN avec la représentation de matrice d'adjacence. C'est peut-être trop de triche: généralement, l'application de la promesse dans un problème de promesse est censée être facile par rapport au problème réel, mais ici, l'application de la promesse que l'entrée est un graphique donne déjà la limite inférieure. Il serait donc agréable de voir un argument pour une borne inférieure de l'espace de journalisation pour le problème de promesse où l'entrée est garantie de provenir de la langue .$\{\{0,1\}^{N \times N} \mid N=1,2,\dots\}$

$\mathbf{ORD}$$s$$t$$G$$\mathsf{L}$

$\mathbf{ORD}$$\mathbf{USTCONN}$$\mathsf{FO}$$\langle G,s,t\rangle$$\mathbf{ORD}$$t$$u \rightarrow v$$\{u,v\}$$\mathbf{USTCONN}$$s,t$