¿Hay alguna justificación para creer que ?

Primero, permítanme citar el escepticismo de que . Como se ha demostrado que la conectividad gráfica no dirigida está en (Reingold) y que (Immerman-Szelepcsényi), creo que la confianza en solo ha disminuido. Algunos investigadores prominentes nunca han tenido una fuerte creencia. Por ejemplo, Juris Hartmanis (fundador del departamento de CS en Cornell y ganador del premio Turing) ha dicho: $L \neq NL$ $L$ $NL=coNL$ $L \neq NL$

Creemos que NLOGSPACE difiere de LOGSPACE, pero no con la misma profundidad de convicción que para las otras clases de complejidad. (Fuente)

Sé que dijo cosas similares en la literatura desde los años 70.

Hay alguna evidencia en contra de , aunque es circunstancial. Se ha trabajado en probar los límites inferiores del espacio para conectividad - (el problema canónico de completo) en modelos computacionales restringidos. Estos modelos son lo suficientemente fuertes como para ejecutar el algoritmo del teorema de Savitch (que proporciona un algoritmo de espacio ) pero probablemente no sean lo suficientemente fuertes como para mejorar asintóticamente. Consulte el documento "Límites inferiores ajustados para la conectividad st en el modelo NNJAG" . Estos límites inferiores de NNJAG muestran que, si es posible vencer el teorema de Savitch e incluso obtener $L=NL$ $s$ $t$ $NL$ $O(\log^2 n)$ $NL \subseteq SPACE[o(\log^2 n)]$ , sin duda, tendrá que idear un algoritmo que sea muy diferente de Savitch.

Aún así, no sé de ninguna consecuencia formal inesperada e inesperada que provenga de (excepto las obvias). Nuevamente, esto se debe principalmente a que ya sabemos cosas como . $L=NL$ $NL=coNL$

Ryan Williams
fuente

Ryan, ¿pueden los modelos en los que puedes probar el límite inferior hacer conectividad no dirigida en el espacio ? Si son modelos no uniformes, supongo que debería ser simple implementar un algoritmo basado en secuencias transversales universales, incluso en un modelo muy restringido

Ω (\log^{2} n)

$\Omega(\log^2 n)$

O (\log n)

$O(\log n)$

Luca Trevisan

@Luca, el periódico que Ryan cita por Edmonds et al. señala que la conectividad no dirigida se puede resolver en el espacio y el tiempo polinómico mediante un algoritmo aleatorio que utiliza secuencias transversales universales. Sospecho que se puede desrandomizar "a la" Reingold mientras permanece dentro del modelo NNJAG, pero no lo he verificado.

O (\log n)

$O(\log n)$

arnab

Creo que el modelo puede hacer conectividad no dirigida en gráficos regulares en el espacio . La página 4 da una descripción del modelo. Se nos permite a pebbles moverse en los nodos del gráfico (para nosotros, sea ), "estados" y una función de transición que toma un estado e índice del nodo pebbled y genera el índice de un borde para mover la piedra a lo largo. (Los bordes de un vértice están indexados .) Usando podemos codificar una secuencia transversal universal. El uso de espacio de un NNJAG se define como que en este caso es .

O (\log n)

$O(\log n)$

p

$p$

p = 1

$p=1$

q

$q$

v

$v$

0, \dots, d

$0,\ldots,d$

q = n^{O (1)}

$q=n^{O(1)}$

p \log n + \log q

$p \log n + \log q$

O (\log n)

$O(\log n)$

Ryan Williams

¿Hay alguna justificación para creer que ?

Respuestas: