Redução direta de

14

Sabemos que a está em pelo teorema do teorema de Immerman – Szelepcsényi e como é portanto, a é reduzida em muitos espaços de log redutível à . Mas existe uma redução direta / combinatória que não passa pelo gráfico de configuração das máquinas de Turing em ?N G s t - c o n n e c t i v i t y N L - h uma r d s t - n o n - c o n n e c t i v i tst-non-connectivityNLst-connectivityNL-hards t - c o n n e c t i v i t y N Lst-non-connectivityst-connectivityNL

stConnectivity (também conhecido como ):stPATH

Dado o gráfico direcionado e os vértices e ,s tGst

Existe um caminho direcionado do vértice para o vértice ?tst


Esclarecimentos:

Você pode assumir que um gráfico é fornecido por sua matriz de adjacência (no entanto, isso não é essencial, pois as representações padrão dos gráficos são conversíveis em espaço de log entre si).

É possível descompactar a prova de da e movê-la para a prova, para que a prova não use esse teorema como um lema. No entanto, esta ainda é a mesma construção essencialmente. O que estou procurando não é isso, quero uma redução conceitualmente direta. Deixe-me fazer uma analogia com o caso . Podemos reduzir vários problemas entre si usando o fato de que eles estão em portanto, reduzir para e s t - c o n n e c t i v i t yNL-hardst-connectivityN P - c o m p L e T um e N P S A T S A TNPNP-completeNPSATSATreduz ao outro problema. E podemos descompactar e combinar essas duas reduções para obter uma redução direta. No entanto, muitas vezes é possível fornecer uma redução conceitualmente muito mais simples que não passa por essa etapa intermediária (você pode remover a menção, mas ela ainda existe conceitualmente). Por exemplo, para reduzir o ou o ou o para , não dizemos que o está em e, portanto, reduz para pois o éV e r t e x C O v e r 3 - C O l o r i n g S A T H um m P um t H N P S A S A T N P - h uma r dHamPathVertexCover3-ColoringSATHamPathNPSASATNP-hard. Podemos fornecer uma fórmula intuitiva simples que seja satisfatória se o gráfico tiver um caminho hamiltoniano. Outro exemplo, temos reduções de outros problemas no para que não dependem de no , por exemplo , , etc, envolvem modificações no gráfico de entrada (e não se referem a nenhuma máquina de Turing que os esteja resolvendo). s t - C o n n e c t i v i t y N L - c o m p l e t e s t - C o n n e c t i v i t y C y C L e S t r o n g l y C o n n eNLst-ConnectivityNL-completest-ConnectivityCycleStronglyConnected

Ainda não vejo nenhuma razão para que isso não possa ser feito. Estou procurando uma redução desse tipo.

Pode ser que isso não seja possível e qualquer redução passaria conceitualmente pelo resultado . No entanto, não vejo por que esse deveria ser o caso, por que a situação seria diferente do caso . Obviamente, para dar uma resposta negativa à minha pergunta, precisaríamos ser mais formais sobre quando é que uma prova conceitualmenteN P N LNL-hardNPinclua outra prova (que é a questão da teoria da prova de que o AFAIK não resolve de maneira satisfatória). No entanto, note que, para uma resposta positiva, não é necessário uma definição formal e espero que seja esse o caso. (Pensarei em como formalizar o que estou pedindo de maneira fiel quando encontrar mais tempo livre. Essencialmente, quero uma redução que funcionaria mesmo se não soubéssemos que o problema está completo para . )NL

Usando a prova de Immerman-Szelepcsenyi teorema é bom, usando ness de e gráfico configuração de um máquina é o que eu quero evitar. s t P A T H N LNL-completestPATHNL

Kaveh
fonte
@ Rafael, eu gosto de usar uma fonte diferente para os nomes de conceitos matemáticos, como classes de complexidade, como é a prática comum na literatura. Por favor, não os remova.
Kaveh
1
Desculpe, mas isso parece horrível . Se necessário, use uma fonte diferente, mas, por favor, seja consistente: você mistura mathsfcom a fonte matemática padrão e até usa fontes diferentes em uma palavra!
Raphael
@ Rafael, eu estou usando-os de forma consistente. Mathsf é usado para distinguir classes de complexidade. Vou pensar sobre a mudança "completa" e "hard" de fora na parte de texto (o problema com isso é que os faria digitou usando fontes diferentes.)
Kaveh
"Consistente" não é igual a "tipograficamente agradável". (Além disso, a distinção não é realmente necessária aqui, especialmente a distinção entre classes e problemas de complexidade (que, aumentando a dor, parece horrível na fonte matemática bruta)).
Raphael
@ Rafael, claro, eu não afirmei isso. Você se opôs à "inconsistência" da maneira como eu as uso, só queria ressaltar que não é esse o caso. Meu estilo é distinguir nomes do conceito matemático como do restante da matemática / texto e eu gostaria de fazê-lo de maneira consistente. Enfim, vou pensar em como torná-lo tipograficamente melhor, preservando o estilo. P
Kaveh

Respostas:

4

É possível, se confuso, converter a prova do teorema de Immerman-Szelepcsényi para a redução desejada. Não há absolutamente nenhuma necessidade de usar o NL-completeness da st-connectivity.

Dada uma instância , construímos um novo gráfico G = ( V , E ) , s , t . Os "vértices principais" de V registram as seguintes informações: a distância atual d de s , o número de vértices de distância no máximo d - 1 , o número de vértices de distância d - 1G=(V,E),s,tG=(V,E),s,tVdsd1d1contados até agora, o vértice atual que estamos adivinhando se ele tem distância no máximo , o número de vértices de distância no máximo d contados até agora, o vértice atual que estamos determinando se ele tem distância no máximo d . Os vértices menores lidam com a parte em que adivinhamos um caminho de comprimento no máximo d - 1 para um vértice que supomos estar na distância no máximo d - 1 . As arestas que envolvem mostrar o vértice t são alcançáveis ​​a partir de sd1ddd1d1tssão descartados. Para cada vértice que estamos testando na distância atual, somente avançamos para o próximo vértice se tivermos contabilizado todos os vértices de menor distância. Ao passar da distância para a distância d + 1 , copiamos as informações necessárias. O vértice inicial s ' explica o fato de que s é o único vértice da distância zero. O vértice final t ' é apontado por todos os vértices que representam o fato de que o processo terminou até (e inclusive) a distância n - 1 , onde n = | V | .dd+1sstn1n=|V|

Como você pode ver, será muito complicado escrever tudo na íntegra e corretamente, mas definitivamente possível. Não foi feito nenhum uso explícito da integridade da NL, pois nunca usamos o gráfico de configuração de nenhuma máquina NL. Isso não é necessário, pois temos algo melhor que o gráfico de configuração - a própria instância de entrada.

Yuval Filmus
fonte