Complejidad de la conectividad st única

Me gustaría saber si el siguiente problema se puede resolver en (espacio de registro no determinista):$\mathsf{NL}$

Dado un grafo dirigido con dos distinguidos vértices y , es que hay un único camino de a en ?$G$$s$$t$$s$$t$$G$

Creo que es probable que esté en ya que podemos decidir si hay una ruta - y si no existe esa ruta. Sin embargo, contar el número de tales caminos es -hard (Valiant, 1979).$\mathsf{NL}$$s$$t$$\mathsf{\sharp P}$

Entonces mis preguntas: ¿Tiene referencias sobre esto? ¿Es obvio que está en ? ¿O que no está en ?$\mathsf{NL}$$\mathsf{NL}$

Parece que tu problema está en . Aquí hay un algoritmo.$NL$

En primer lugar, nondeterministically adivinar un camino de a . Si adivinas incorrectamente, rechaza . Llame a este algoritmo .t $s$$t$$A$

Considere el siguiente algoritmo no determinista , que determina si hay al menos dos rutas. Dado un gráfico , para todos los pares de aristas distintas , adivine una ruta de a que incluya pero no , luego adivine una ruta de a que incluya pero no . Si las conjeturas son correctas, acepte . Si no hay aceptación para todas las opciones de y , rechazar . Nota es implementable en espacio de registro no determinista.s , t e , f s t e f s t f e e f $B$$s,t$$e,f$$s$$t$$e$$f$$s$$t$$f$$e$$e$$f$$B$

Ahora, el conjunto es el conjunto de gráficos - con al menos dos rutas de a . Debido , el complemento de es también en , es decir, podemos determinar si y tienen menos de dos caminos, en logspace no determinista.s t s t N L = c o N L B N L s $L(B)$$s$$t$$s$$t$$NL = coNL$$B$$NL$$s$$t$

El algoritmo final es: "Ejecutar Si acepta, ejecute el complemento de y envíe su respuesta".A $A$$A$$B$

No sé de una referencia.

ACTUALIZACIÓN: Si realmente desea una referencia, consulte el primer párrafo de la Sección 3 de este documento . Pero esta es probablemente solo una de las muchas referencias que citan esta consecuencia. Sería más razonable llamar al resultado "folklore" en lugar de citar un artículo que lo menciona.

ACTUALIZACIÓN 2: Supongamos que desea determinar si hay una ruta simple única. En ese caso, el algoritmo no tiene que cambiar: si hay una ruta, entonces hay una ruta simple. Creo que la siguiente modificación trabajará para el algoritmo .$A$$B$

Queremos reescribir el algoritmo para que acepte si hay al menos dos rutas simples.$B$

Primero considere el siguiente algoritmo de tiempo polinómico para el problema. Encontrar un camino más corto desde a . Para cada borde en , verifique si hay otra ruta - que no pase por . Si encuentra ese camino, acepte . Si nunca encuentras otro camino, rechaza . Debido a que es el más corto, no tiene un ciclo, y si hay otra ruta que no usa algún borde de , entonces hay otra ruta que es simple y no usa algún borde des t e P s t e P P $P$$s$$t$$e$$P$$s$$t$$e$$P$$P$$P$. (Este algoritmo se usa para el problema del "segundo camino más corto").

Implementaremos este algoritmo en . Si tuviéramos un algoritmo para consultar los bordes en una ruta fija , podríamos implementar lo anterior en un espacio de registro no determinista: iterando a través de todos los bordes en , adivine una ruta - y verifique eso para cada borde visitado en el camino , ninguno de ellos es igual a .$NL$$NL$$e$$P$$e$$P$$s$$t$$e$

Entonces, lo que necesitamos es un "oráculo de ruta", un algoritmo con la propiedad: dado , en cada ruta de cálculo, el algoritmo informa el borde en una ruta - fija particular , o rechazar . Podemos obtener un oráculo de ruta usando para aislar la primera ruta lexicográfica.$NL$$i=1,\ldots,n$$i$$s$$t$$NL=coNL$

Aquí hay un bosquejo del oráculo del camino.

Encuentre , la longitud del camino más corto de a , probando todos usando .$k$$s$$t$$k=1,\ldots,n$$NL=coNL$

Establezca las variables , , .$u:=s$$x:=1$$j:=k$

Para todos los vecinos de en orden lexicográfico,$v$$u$

Determine si existe o no una ruta desde hasta de longitud (utilizando el resultado ). Más precisamente, ejecute el algoritmo no determinista para conectividad - (de longitud ) y el algoritmo para su complemento, simultáneamente. Cuando uno de ellos acepta, vaya con su respuesta (debe ser correcta; ambos no pueden aceptar). Si ambos rechazan, rechace .t j - 1 N L = c o N L s t j - $v$$t$$j-1$$NL=coNL$$s$$t$$j-1$

Si no hay camino, continúe con el próximo vecino. Si has agotado a todos los vecinos, rechaza .

Si hay un camino, a continuación, si , la salida como el ésimo borde en el camino de a . De lo contrario, incremente , disminuya , establezca e inicie el ciclo for nuevamente si .( u , v ) i s t x j u : = v v ≠ $x=i$$(u,v)$$i$$s$$t$$x$$j$$u := v$$v \neq t$

Si después de alcanzar salida mal (lo dado era demasiado grande).t i$x < i$$t$$i$$i$

Dado , este algoritmo da salida a ya sea el ésimo borde en el camino lexicográficamente más corto de a , o rechazos.i P s $i$$i$$P$$s$$t$