Como provar que o USTCONN requer espaço logarítmico?

19

USTCONN é o problema que requer a decisão de saber se existe um caminho do vértice de origem para o vértice de destino t em um gráfico G , onde todos são dados como parte da entrada.stG

Omer Reingold mostrou que USTCONN está em L (doi: 10.1145 / 1391289.1391291 ). A prova constrói um expansor de grau constante por meio do produto zig-zag. Um expansor de grau constante tem diâmetro logarítmico e é possível verificar todos os caminhos possíveis usando um número constante de marcadores de tamanho logarítmico.

O resultado de Reingold fornece um limite superior logarítmico à complexidade espacial do USTCONN, resolvendo sua complexidade espacial "até um fator constante", de acordo com o artigo. Estou curioso sobre o limite inferior correspondente, que não é mencionado em nenhum outro lugar do artigo.

Como provar que é necessário espaço logarítmico para decidir a USTCONN no pior dos casos?

Editar: Fixar a representação de entrada ser a matriz adjacência do subjacente N -vertex gráfico simples simétrico dirigido, com as linhas listadas consecutivamente para formar um N 2 cadeia de bits.N×NNN2


Lewis e Papadimitriou mostraram (doi: 10.1016 / 0304-3975 (82) 90058-5 ) que USTCONN é SL completo, o que com o resultado de Reingold implica que SL = L. Savitch mostrou (doi: 10.1016 / S0022-0000 (70) 80006-X ) que . DSPACE adicional ( f ( n ) ) = DSPACE ( 1 ) para qualquer função computável f ( n ) = o ( log log n )NSPACE(n)DSPACE(n2)DSPACE(f(n))=DSPACE(1 1)f(n)=o(registroregistron) por Stearns, Hartmanis e Lewis (doi: 10.1109 / FOCS.1965.11 ), portanto, pelo menos é necessário espaço para o USTCONN. Finalmente, as classes usuais conhecidas como abaixo de L (como NC 1 ) são definidas em termos de circuitos e não são obviamente comparáveis ​​a qualquer classe definida em termos de um espaço limitado.Ω(registroregistron)NC1 1

Até onde eu posso ver, isso deixa em aberto a possibilidade (reconhecidamente improvável) de que exista um algoritmo determinístico ainda melhor que use apenas espaço mas Ω ( log log n ) , para alguns δ < 1 , ou mesmo um algoritmo não determinístico para USTCONN que usa o (O((logn)δ)Ω(loglogn)δ<1 espaço.o((logn)1/2)

Pelo teorema da hierarquia espacial , contanto que f (DSPACE(o(f(n))DSPACE(f(n)) seja construtível em espaço.Isso pode sugerir que USTCONN não pode estar em DSPACE ( o ( log n ) )f(n)DSPACE(o(logn)). No entanto, o USTCONN estar completo para L em reduções de espaço de log não parece implicar isso. Parece ainda possível que o USTCONN tenha estrutura suficiente para codificar qualquer problema em L por meio de uma redução do espaço de log, mas o próprio USTCONN requer apenas espaço sublogarítmico.

Desde que exista alguma linguagem em L que exija espaço logarítmico, a exibição de USTCONN está completa para L sob um estritamente "mais fraco" do que a redução do espaço de log produziria o limite inferior desejado.

O USTCONN está completo para L sob uma redução que requer espaço?o(logn)

Immerman mostrou (doi: 10.1137 / 0216051 ) que uma versão de acessibilidade direcionada na qual o caminho desejado (mas não o próprio gráfico) é determinístico, é completa para L sob reduções de primeira ordem, que são computáveis ​​por circuitos AC 0 . Talvez isso possa ser adaptado para mostrar que o USTCONN está completo para L com reduções de FO. No entanto, embora a CA0 esteja estritamente contido em L, o AC 0 é novamente uma classe de circuito e eu não conheço nenhuma maneira de executar reduções de FO no espaço sublogarítmico.00


Editar 14-07-2015: É uma questão filosófica interessante se o uso de espaço de uma TM deve incluir o tamanho de um índice na entrada (permitindo acesso aleatório à entrada, mas precisando de um bit extra se a entrada dobrar de tamanho ) ou se o espaço usado por uma TM é o número de quadrados da worktape visitados durante um cálculo (que assume que o cabeçote da fita de entrada está fixo e não muda quando a fita de entrada dobra de tamanho). A antiga definição de estilo RAM fornece imediatamente um espaço de log mais baixo para qualquercomputação e modelos de computadores atuais que controlam a posição atual em um arquivo como um deslocamento desde o início do arquivo. A última definição clássica assume uma fita semelhante a papel com uma cabeça de leitura fixa que não sabe nada sobre a fita além do símbolo de entrada atual, que possivelmente é o que Turing pretendia em seu artigo de 1937.

Argumentos heurísticos, como o comentário de Thomas, de que nem mesmo é possível indexar a entrada com bits de espaço, parecem assumir uma definição moderna no estilo RAM. Stearns / Hartmanis / Lewis usam a definição de estilo TM, assim como a maioria dos clássicos trabalha em computação limitada por espaço.o(logn)

Pode-se provar um limite inferior do espaço de log para USTCONN representado como uma matriz de adjacência, observando que a linguagem unária dos quadrados perfeitos exige que o espaço de log seja reconhecido (consulte Rūsiņš Freivalds, Modelos de Computação, Hipótese de Riemann e Matemática Clássica , SOFSEM 1998, LNCS 1521, 89 –106. Doi: 10.1007 / 3-540-49477-4_6 ( pré-impressão)). Em seguida, o mesmo limite inferior se aplica ao USTCONN com a representação da matriz de adjacência. Talvez isso seja uma trapaça: normalmente, impor a promessa em um problema de promessa deve ser fácil comparado ao problema real, mas aqui impor a promessa de que a entrada é um gráfico já fornece o limite inferior. Portanto, seria bom ver um argumento para um limite inferior do espaço de log para o problema da promessa, onde a entrada é garantida como sendo do idioma .{{0,1}N×NN=1,2,}

András Salamon
fonte
Sua conclusão ", pelo menos ... é necessário espaço para UStCONN" não segue do restante de sua frase, pois existem funções em para as quais esse δ não existe.o(log(log(n)))δ
5
A representação de entrada se torna importante, pois com espaço não podemos especificar ou acessar um local arbitrário na entrada. Que representação de entrada você está usando? Podemos mostrar que o USTCONN está no espaço sub-logarítmico não determinístico? o(logn)
Thomas suporta Monica
FO = LTH = dlogtime AC uniforme ^ 0
Kaveh
isso é muito detalhado e ótimo, mas parece que ajudaria a relacionar isso com "problemas abertos oficialmente reconhecidos / reconhecidos" e também com problemas completos conhecidos (veja alguns deles, mas talvez mais por aí?) ... dos quais aparentemente é bem próximo ... e note que se não é um bom formato para isso, se for o caso ... btw o U no USTConn parece representar Indireto, certo? fyi SJ neste site tem estudado "baixo nível" STConn reduzir limites e sua inter-relação com USTConn, ofc parece não haveria conexões muito naturais
vzn
Talvez a técnica de complexidade da comunicação para provar o limite inferior do espaço de tempo possa ajudar: se o espaço for menor que , o tempo será menor que n 2, portanto o tempo do espaço será menor que n 2 log n . De alguma forma, podemos nos livrar do log n no espaço-tempo e mostrar se o espaço é menor que o log n, e o espaço-tempo é menor que n 2 ? lognn2n2lognlognlognn2
Kaveh

Respostas:

13

O artigo Counting Quantifiers, Successor Relations e Logarithmic Space , de Kousha Etessami, prova que o problema (que consiste essencialmente em verificar se um vértice s precede um vértice t em um gráfico G de grau inferior , que promete ser um caminho) é euORDstGeu duro sob projeções livres de quantificador.

O problema pode ser vista para reduzir o problema L S T C O N N , por F ó -reductions: Dado um exemplo L , s , t de S R D apenas eliminar a borda de T e de saída as outras bordas u v como arestas undirected { u , v } a L S T C S N N questão sendo seORDvocêSTCONNFOG,s,tORDtvocêv{você,v}vocêSTCONN estão conectados no gráfico resultante. (Nota: a redução provavelmente pode ser ainda mais fina.)s,t

SamiD
fonte
11
Obrigado! Esta parece ser uma elaboração do meu comentário final sobre a completude em L do USTCONN. No entanto, não está claro para mim que a redução do ORD possa ser feita no espaço sublogarítmico, portanto isso não parece responder à pergunta principal, de mostrar que o USTCONN realmente exige pelo menos espaço logarítmico. o que estou perdendo?
András Salamon
11
@AndrasSalamon: Você está perdendo a pergunta de Thomas sobre representação de entrada, mesmo que isso não atenda à pergunta que você acabou de fazer.