Réduction directe de à

Nous savons que la est dans par le théorème du théorème d' Immerman-Szelepcsényi et puisque la est par conséquent, la est un espace de journalisation multiple réductible à la . Mais y a-t-il une réduction directe / combinatoire qui ne passe pas par le graphe de configuration des machines de Turing dans ?$st\text{-}non\text{-}connectivity$$\mathsf{NL}$$st\text{-}connectivity$$\mathsf{NL\text{-}hard}$$st\text{-}non\text{-}connectivity$$st\text{-}connectivity$$\mathsf{NL}$

$\mathsf{stConnectivity}$ (alias ):$stPATH$

Étant donné le graphe dirigé et les sommets et ,$G$$s$$t$

Y a-t-il un chemin dirigé du sommet au sommet ?$s$$t$

Clarifications:

Vous pouvez supposer qu'un graphe est donné par sa matrice d'adjacence (mais cela n'est pas essentiel car les représentations standard des graphes sont convertibles en espace logarithmique).

Il est possible de décompresser la preuve de la de la et de la déplacer dans la preuve afin que la preuve ne l'utilise pas comme théorème comme lemme. Cependant, il s'agit essentiellement de la même construction. Ce que je recherche, ce n'est pas ça, je veux une réduction conceptuellement directe. Permettez-moi de faire une analogie avec le cas . Nous pouvons réduire divers problèmes uns aux autres en utilisant le fait qu'ils sont dans donc réduire à SAT et SAT$\mathsf{NL\text{-}hard}$$st\text{-}connectivity$$\mathsf{NP}$$\mathsf{NP\text{-}complete}$$\mathsf{NP}$$SAT$$SAT$se réduit à l'autre problème. Et nous pouvons déballer et combiner ces deux réductions pour obtenir une réduction directe. Cependant, il est souvent possible de donner une réduction conceptuellement beaucoup plus simple qui ne passe pas par cette étape intermédiaire (vous pouvez supprimer la mention, mais elle est toujours là conceptuellement). Par exemple, pour réduire ou ou to nous ne disons pas que est dans et se réduit donc à puisque est$HamPath$$VertexCover$$3\text{-}Coloring$$SAT$$HamPath$$\mathsf{NP}$$SA$$SAT$$\mathsf{NP\text{-}hard}$. Nous pouvons donner une formule intuitive simple qui est satisfiable si le graphe a un chemin hamiltonien. Un autre exemple, nous avons des réductions d'autres problèmes dans à qui ne dépendent pas de ness de , par exemple , , etc., ils impliquent une modification sur le graphique d'entrée (et ne se réfèrent à aucune machine de Turing qui les résout).$\mathsf{NL}$$st\text{-}Connectivity$$\mathsf{NL\text{-}complete}$$st\text{-}Connectivity$$Cycle$$StronglyConnected$

Je ne vois toujours aucune raison pour laquelle cela ne peut pas être fait pour celui-ci. Je recherche une réduction de ce type.

Il se peut que cela ne soit pas possible et toute réduction passe conceptuellement par le résultat de ness. Cependant, je ne vois pas pourquoi cela devrait être le cas, pourquoi la situation serait différente du cas . Il est évident que de donner une réponse négative à ma question que nous devons être plus formel à propos de quand une preuve conceptuelle$\mathsf{NL\text{-}hard}$$\mathsf{NP}$inclure une autre preuve (qui est la question de la théorie de la preuve que l'AFAIK ne règle pas de manière satisfaisante). Cependant, notez que pour une réponse positive, il n'est pas nécessaire d'avoir une telle définition formelle et j'espère que c'est le cas. (Je réfléchirai à la manière de formaliser ce que je demande de manière fidèle lorsque je trouverai plus de temps libre. Essentiellement, je veux une réduction qui fonctionnerait même si nous ne savions pas que le problème était complet pour . )$\mathsf{NL}$

Utiliser la preuve du théorème Immerman-Szelepcsényi est bien, utiliser ce que je veux éviter en utilisant ness de et le graphe de configuration d'une machine .$\mathsf{NL\text{-}complete}$$stPATH$$\mathsf{NL}$

Il est possible, en cas de désordre, de convertir la preuve du théorème Immerman-Szelepcsényi en la réduction souhaitée. Il n'est absolument pas nécessaire d'utiliser l'exhaustivité NL de la connectivité st.

Etant donné une instance , nous construisons un nouveau graphe . Les "sommets majeurs" de enregistrent les informations suivantes: la distance courante de , le nombre de sommets de distance au plus , le nombre de sommets de distance comptés jusqu'à présent, le sommet courant we' re deviner s'il a une distance au plus , le nombre de sommets de distance au plus comptés jusqu'à présent, le sommet actuel nous déterminons s'il a une distance au plus . Les sommets mineurs gèrent la partie où l'on devine un chemin de longueur au plus$G=(V,E),s,t$$G'=(V',E'),s',t'$$V'$$d$$s$$d-1$$d-1$$d-1$$d$$d$$d-1$à un sommet que nous supposons être de distance au plus . Les arêtes qui impliquent de montrer que le sommet est accessible à partir de sont supprimées. Pour chaque sommet que nous testons à la distance actuelle, nous n'avançons vers le sommet suivant que si nous avons pris en compte tous les sommets de plus petite distance. Lors du passage de la distance à la distance , nous copions les informations requises. Le sommet de départ tient compte du fait que est le seul sommet de la distance zéro. Le sommet final est pointé par tous les sommets représentant le fait que le processus a terminé jusqu'à (et y compris) la distance , où$d-1$$t$$s$$d$$d+1$$s'$$s$$t'$$n-1$$n=|V|$.

Comme vous pouvez le voir, il sera assez compliqué d'écrire tout en entier et correctement, mais certainement possible. Aucune utilisation manifeste de la complétude NL n'a été faite, en ce sens que nous n'utilisons jamais le graphique de configuration d'une machine NL. Ce n'est pas nécessaire, car nous avons quelque chose de mieux que le graphe de configuration - l'instance d'entrée elle-même.