Complejidad: ¿por qué RL=NL si no se exige un tiempo de ejecución polinómico?

Question

La clase de complejidad RL se describe en el zoo de complejidad como: Tiene la misma relación con L que RP con P. La máquina aleatoria debe detenerse con probabilidad 1 en cualquier entrada. También debe ejecutarse en tiempo polinómico (ya que de lo contrario sólo obtendríamos NL).

La pregunta es: ¿cómo podemos obtener NL si omitimos la demanda de tiempo polinómico? Tengo una solución propia pero me parece extraña.

Mi solución: Si basta con resolver ST-CON. Podemos utilizar el mismo algoritmo NL para ST-CON (adivinar un camino) con una diferencia importante - contamos el número de pasos que damos, y si suprime el número de vértices del grafo, reiniciamos el cálculo, sin recordar NADA.

Esto significa que podemos jugar a este juego indefinidamente. Si el grafo no está conectado a ST, entonces nunca nos detendremos, pero si está conectado a ST nos detendremos con probabilidad 1 (esto es lo mismo que decir que una variable aleatoria geométrica obtiene un valor finito con probabilidad 1). Sin embargo, dado que no nos detenemos para las NO-instancias, esta solución "me parece mal".

¿Hay otra solución? ¿Es correcta mi solución?

Answer 1

Su solución es casi correcta.

En la definición de RL, exigimos que el algoritmo se detenga con probabilidad $1$ en cualquier entrada. Como usted nota, su algoritmo se ejecuta para siempre en "No" instancias. Para solucionar esto, vamos a aprovechar el hecho de que se nos permite una pequeña posibilidad de error. En concreto, se nos permite rechazar a veces instancias "Sí", siempre y cuando nunca aceptemos una instancia "No".

La idea básica es mantener un contador de cuántas iteraciones hemos utilizado hasta ahora. Si existe un camino, deberíamos encontrarlo dentro de $2N^N$ iteraciones (con una probabilidad mínima de $3/4$ ). Así que si hemos pasado tanto tiempo sin encontrar un camino válido, rechazaremos el grafo. Ten en cuenta que nunca aceptaremos un grafo malo de esta forma, y raramente rechazaremos un grafo bueno.

No podemos contar ingenuamente con $N^N$ Sin embargo, ya que esto requeriría $N\lg N$ espacio. En su lugar, "contaremos" probabilísticamente hasta ese punto.

Después de cada iteración, voltearemos $N\lg N + 2$ monedas. Si todas las monedas salen cara, nos detenemos (y rechazamos el gráfico). Si al menos una moneda sale cruz, comenzamos otra iteración. Esto se puede hacer en el espacio logarítmico, ya que sólo tenemos que contar cuántos lanzamientos se han producido.

La probabilidad de obtener todas las cabezas es $1/2^{N\lg N + 2}=1/4N^N$ por lo que con probabilidad al menos $3/4$ Esto no ocurrirá hasta al menos $2N^N$ iteraciones.

Tomando un límite de unión sobre las dos formas en que el algoritmo podría fallar, vemos que todo funciona con una probabilidad de al menos $1/2$ .

Por último, observe que esto se detiene con probabilidad $1$ ya que eventualmente voltearemos todas las cabezas.