Algorithmes SC ^ 2 pour la connectivité st

Savitch a donné un algorithme déterministe pour résoudre la st-connectivité en utilisant l' espace , impliquant . L'algorithme de Savitch s'exécute dans le temps 2 ^ {O ({\ log} ^ 2 {n})} . C'est un problème ouvert majeur si la connectivité st peut être résolue par un algorithme déterministe dans le temps polynomial et l' espace O ({\ log} ^ 2 {n}) c'est-à-dire si NL \ subseteq SC ^ 2 . RL , qui se situe entre L et NL , est connu dans SC ^ 2 . Par conséquent, l'accessibilité dans les graphiques dirigés avec un temps de mélange polynomial est dans SC ^ 2 .N L ⊆ D S P A C E ( log 2 n ) 2 O ( log 2 n ) O ( log 2 n ) N L ⊆ S C 2 R L L N $O({\log}^2{n})$$NL \subseteq DSPACE({\log}^2{n})$$2^{O({\log}^2{n})}$$O({\log}^2{n})$$NL \subseteq SC^2$$RL$$L$$NL$ S C $SC^2$$SC^2$

Je recherche des cas particuliers de st-connectivité (qui ne sont pas connus pour être en $L$ ) qui ont des algorithmes $SC^2$ . Connaît-on les graphes planaires, les DAG planaires? Notez que st-connectivité dans les DAG reste NL-complete.

Il existe deux classes de complexité liées dans $\text{NL}$ qui se trouvent également dans $\text{LogDCFL}$ , ce qui les place dans $\text{SC}^2$ (par Cook ).

• Le premier est $\text{RUL}$ , pour "Reach-Unambiguous Log-space" qui a une accessibilité dans les mangroves (graphiques où chaque paire de sommets a au plus un chemin dirigé entre eux) comme un problème complet. Cette classe a déjà été discutée .
• Le second est $\text{ReachFewL}$ , qui a une accessibilité complète pour les graphiques avec au plus un nombre polynomial de chemins entre n'importe quelle paire de sommets.

L'exécution d'une recherche en profondeur sur ces graphiques à l'aide d'une pile a la garantie que cela prendra du temps polynomial, donc ces classes sont dans .$\text{LogDCFL} \subseteq \text{SC}^2$

$O(\log n)$$O(\log n)$

Voici également une récente enquête d'Allender: "Problèmes d'accessibilité: une mise à jour"