Há alguma justificação para acreditar que

Primeiro, deixe-me citar o ceticismo de que . Como foi demonstrado que a conectividade gráfica não direcionada está em (Reingold) e que (Immerman-Szelepcsényi), acho que a confiança em só diminuiu. Alguns pesquisadores de destaque nunca tiveram uma crença forte. Por exemplo, Juris Hartmanis (fundador do departamento de CS da Cornell and Turing, vencedor do prêmio) disse: $L \neq NL$ $L$ $NL=coNL$ $L \neq NL$

Acreditamos que NLOGSPACE difere de LOGSPACE, mas não com a mesma profundidade de convicção que nas outras classes de complexidade. (Fonte)

Eu sei que ele disse coisas semelhantes na literatura desde os anos 70.

Há alguma evidência contra , embora seja circunstancial. Houve trabalho em provar espaço abaixar limites para - conectividade (o canônica problema -completo) em modelos computacionais restritas. Esses modelos são fortes o suficiente para executar o algoritmo do teorema de Savitch (que fornece um algoritmo de espaço ), mas não são comprovadamente fortes o suficiente para se assintoticamente melhor. Consulte o artigo "Limites inferiores apertados para conectividade st no modelo NNJAG" $L=NL$ $s$ $t$ $NL$ $O(\log^2 n)$ . Esses limites inferiores do NNJAG mostram que, se é possível vencer o teorema de Savitch e até obter , certamente será necessário criar um algoritmo muito diferente do Savitch. $NL \subseteq SPACE[o(\log^2 n)]$

Ainda assim, não conheço nenhuma consequência formal improvável e inesperada que venha de (exceto as óbvias). Novamente, isso ocorre principalmente porque já sabemos coisas como . $L=NL$ $NL=coNL$

Ryan Williams
fonte

Ryan, os modelos nos quais você pode provar o limite inferior fazer conectividade não direcionada no espaço ? Se eles são modelos não uniformes, eu acho que deveria ser simples de implementar um algoritmo baseado em seqüências de passagem universais, mesmo em um modelo muito restrito

Ω (\log^{2} n)

$\Omega(\log^2 n)$

O (\log n)

$O(\log n)$

Luca Trevisan

@Luca, o artigo que Ryan cita por Edmonds et al. observa que a conectividade não direcionada pode ser resolvida no espaço e no tempo polinomial por um algoritmo aleatório usando sequências transversais universais. Suspeito que possa ser derandomizado "a la" Reingold enquanto estiver dentro do modelo NNJAG, mas não verifiquei.

O (\log n)

$O(\log n)$

22611 arnab

Eu acho que o modelo pode fazer conectividade não direcionada em gráficos regulares no espaço . A página 4 fornece uma descrição do modelo. É permitido que seixos se movam nos nós do gráfico (para nós, vamos ), "estados" e uma função de transição que pega um estado e um índice do nó seixo e gera o índice de uma aresta para mover a pedra. (As arestas de um vértice são indexadas .) Usando os estados , podemos codificar uma sequência transversal universal. O uso de espaço de um NNJAG é definido como que neste caso é .

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

Há alguma justificação para acreditar que

Respostas: