Reducción directa de

14

Sabemos que st-non-connectivity está en NL según el teorema del teorema de Immerman – Szelepcsényi y dado que st-connectivity es NL-hard por lo tanto es un espacio logarítmico de muchos reductibles a s t - c o n n e c t i v i t y . ¿Pero hay una reducción directa / combinatoria que no pasa por el gráfico de configuración de las máquinas de Turing en N L ?st-non-connectivityst-connectivityNL

stConnectivity (también conocido como):stPATH

Dada grafo dirigido y vértices s y t ,Gst

¿Hay una ruta dirigida desde el vértice al vértice t ?st


Aclaraciones:

Puede suponer que un gráfico viene dado por su matriz de adyacencia (sin embargo, esto no es esencial ya que las representaciones estándar de los gráficos son convertibles en espacio logarítmico entre sí).

Es posible desempaquetar la prueba de ness de s t - c o n n e c t i v i t y y moverla a la prueba para que la prueba no lo use ese teorema como lema . Sin embargo, esta sigue siendo la misma construcción esencialmente. Lo que estoy buscando no es esto, quiero una reducción conceptual directa. Permítanme dar una analogía con el caso N P. Podemos reducir varios N P - c o m p lNL-hardst-connectivityNP problemas entre sí usando el hecho de que están en N P , por tanto, reducir al S A T y S A T reduce al otro problema. Y podemos desempaquetar y combinar estas dos reducciones para obtener una reducción directa. Sin embargo, a menudo es posible dar una reducción conceptual mucho más simple que no pasa por este paso intermedio (puede eliminar mencionarlo, pero todavía está allí conceptualmente). Por ejemplo, para reducir H un m P un t h o V e r t e x C o vNP-completeNPSATSATHamPath o 3 - C o l o r i n g a S A T no decimos H un m P un t h está en N P y por lo tanto se reduce a S A desde S A T es N P - h una r d . Podemos dar una fórmula intuitiva simple que sea satisfactoria si el gráfico tiene una ruta hamiltoniana. Otro ejemplo, tenemos reducciones de otros problemas en NVertexCover3-ColoringSATHamPathNPSASATNP-hard a s t - C o n n e c t i v i camiseta T y que no se basan en N L - c o m p l e t e Ness de s t - C o n n e c t i v i t y , p. ej. C y c l e , S t r o n gNLst-ConnectivityNL-completest-ConnectivityCycle , etc, que implican la modificación en el gráfico de entrada (y no se refieren a cualquier máquina de Turing que les es resolver).StronglyConnected

Todavía no veo ninguna razón por la cual esto no se puede hacer para este. Estoy buscando una reducción de este tipo.

Podría ser el caso de que esto no es posible y cualquier reducción sería conceptualmente ir a través de la Ness resultado. Sin embargo, no veo por qué ese debería ser el caso, por qué la situación sería diferente del caso N P. Obviamente, para dar una respuesta negativa a mi pregunta, deberíamos ser más formales sobre cuándo una prueba conceptualNL-hardNPincluya otra prueba (que es la pregunta de la teoría de la prueba de que AFAIK no se resuelve de manera satisfactoria). Sin embargo, tenga en cuenta que para una respuesta positiva uno no necesita una definición tan formal y espero que ese sea el caso. (Pensaré en cómo formalizar lo que pido de manera fiel cuando encuentre más tiempo libre. Esencialmente, quiero una reducción que funcione incluso si no supiéramos que el problema está completo para ).NL

Usando la prueba de Immerman-Szelepcsényi teorema es fina, utilizando Ness de s t P A T H y el gráfico de configuración de un N L máquina es lo que desea evitar.NL-completestPATHNL

Kaveh
fuente
@Raphael, me gusta usar una fuente diferente para los nombres de conceptos matemáticos como las clases de complejidad, como es la práctica común en la literatura. Por favor no los elimines.
Kaveh
1
Lo siento, pero eso se ve horrible . Si es necesario, use una fuente diferente, pero luego sea coherente: mezcle mathsfcon una fuente matemática estándar, ¡e incluso use fuentes diferentes en una palabra!
Raphael
@Raphael, los estoy usando de manera consistente. Mathsf se usa para distinguir clases de complejidad. Pensaré en mover "completo" y "duro" afuera a la parte de texto (el problema con eso es que los haría escribir con diferentes tipos de letra).
Kaveh
"Consistente" no es igual a "tipográficamente agradable". (Además, la distinción no es realmente necesaria aquí, especialmente la que existe entre las clases de complejidad y los problemas (que, además del dolor, se ve horrible en la fuente matemática)).
Raphael
@Raphael, claro, no dije eso. Se opuso a la "inconsistencia" de la forma en que los uso, solo quería señalar que ese no es el caso. Mi estilo es distinguir nombres de conceptos matemáticos como del resto de matemática / texto y me gustaría hacerlo de manera consistente. De todos modos, pensaré en cómo hacer que sea tipográficamente más agradable mientras se conserva el estilo. P
Kaveh

Respuestas:

4

Es posible, si es desordenado, convertir la prueba del teorema Immerman-Szelepcsényi a la reducción que desee. No hay absolutamente ninguna necesidad de utilizar la integridad de NL de la conectividad st.

Dada una instancia , construimos un nuevo gráfico G = ( V , E ) , s , t . Los "vértices mayores" de V ' registran la siguiente información: la distancia actual d desde s , el número de vértices de distancia como máximo d - 1 , el número de vértices de distancia d - 1G=(V,E),s,tG=(V,E),s,tVdsd1d1contado hasta ahora, el vértice actual que estamos adivinando si tiene distancia como máximo , el número de vértices de distancia como máximo d contado hasta ahora, el vértice actual que estamos determinando si tiene distancia como máximo d . Los vértices menores manejan la parte donde adivinamos un camino de longitud como máximo d - 1 a un vértice que suponemos que es de distancia como máximo d - 1 . Los bordes que implican mostrar el vértice t son accesibles desde sd1ddd1d1tsse caen Para cada vértice que estamos probando a la distancia actual, solo avanzamos al siguiente vértice si hemos tenido en cuenta todos los vértices de menor distancia. Al pasar de la distancia a la distancia d + 1 , copiamos la información requerida. El vértice inicial s ' explica el hecho de que s es el único vértice de la distancia cero. El vértice final t ' es señalado por todos los vértices que representan el hecho de que el proceso ha terminado hasta (e incluyendo) la distancia n - 1 , donde n = | V | .dd+1sstn1n=|V|

Como puede ver, será bastante complicado escribir todo completo y correctamente, pero definitivamente es posible. No se hizo un uso manifiesto de la integridad de NL, ya que nunca usamos el gráfico de configuración de ninguna máquina de NL. Eso no es necesario, ya que tenemos algo mejor que el gráfico de configuración: la instancia de entrada en sí.

Yuval Filmus
fuente