Separando espaço de log do tempo polinomial

24

É claro que qualquer problema que seja decidível no espaço de log determinístico ( ) é executado no máximo no tempo polinomial ( ). Existe uma grande variedade de classes de complexidade entre e . Exemplos incluem , , , , , . Acredita-se que .P L P N L L o g C F G N C I S A C i A C I S C i G PLPLPNLLogCFLNCiSACiACiSCiLP

Em uma das minhas mensagens g I mencionados duas abordagens (juntamente com os correspondentes conjecturas) em direcção provando . Ambas as abordagens são baseadas em programas de ramificação e têm 20 anos de diferença !! Há outras abordagens e / ou no sentido de conjecturas separação de (ou) a separação de quaisquer classes intermediárias entre e .L P L PLPLPLP

Shiva Kintali
fonte
acho que este problema de compressão de uma sequência TM prazo está relacionada
vzn

Respostas:

21

Os limites inferiores da profundidade do circuito (equivalentemente, os limites inferiores do tamanho da fórmula) são provavelmente a abordagem mais natural: Um limite superior de profundidade Super- para um problema em separaria de e a técnica de complexidade da comunicação Karchmer-Wigderson pode ser a técnica natural para isso.P P Llog2(n)PPL

Noam
fonte
3
Os obstáculos à prova natural não seriam um problema aqui? Estou curioso por que isso seria assim.
Suresh Venkat
6
Sim, definitivamente parece que essa prova teria que ser "não natural", mas, pelo que entendi, precisariam ser as outras abordagens mencionadas na postagem do blog.
Noam
8

[1] comprova um limite inferior para instâncias de fluxo de mincost cujos tamanhos de bits são suficientemente grandes (mas ainda lineares) em comparação com o tamanho do gráfico e, além disso, provou que se alguém pudesse mostrar o mesmo limite inferior para entradas de valores suficientemente pequenos tamanho de bit implicaria (e, portanto, ). Isso é, em um nível alto, o mesmo que a resposta de Noam no sentido de provar limites inferiores da profundidade do circuito (= limites inferiores do tamanho da fórmula), mas parece ser uma direção muito diferente dos jogos de Karchmer-Wigderson.PLPNCPL

Mais detalhadamente, [1] mostra o seguinte. Usando a mesma notação do papel, deixe denotar a linguagem de fluxo de custo mínimo. Podemos pensar na linguagem de fluxo de custo mínimo nos gráficos vertex, denominada , como um subconjunto de para alguns , com números inteiros codificados por cadeias de bits. Deixe denotar o conjunto de todos os vetores em onde cada coordenada inteira tem tamanho de bit no máximo . Dada uma função (especificaremos que tipo de função posteriormente), dizemos que separa dentro den L ( n ) Z k ( n ) k ( n ) = Θ ( n 2 ) B ( a , n ) Z k ( n ) a n f ( x 1 , , x k ) f L ( n ) B ( a , n ) L ( n ) BLnL(n)Zk(n)k(n)=Θ(n2)B(a,n)Zk(n)anf(x1,,xk)fL(n)B(a,n)se os pontos em são exatamente aqueles tais que .xB ( um , n ) f ( x ) = 1L(n)B(a,n)xB(a,n)f(x)=1

Proposição [1, Proposição 7.3] Se for separado em por onde é uma matriz de tamanho cujas entradas são combinações lineares (complexas) de e tais que , em seguida, .B ( a , n ) det ( M ( x ) ), x k a < 1 / ( 2 d ) PN CL(n)B(a,n)det(M(x))2 n / d x 1 ,M2n/dx1,,xka<1/(2d)PNC

A relação entre o bit-bound e o tamanho bound é crucial aqui. No mesmo artigo, ele mostrou:2 n / dan2n/d

Teorema [1, Teorema 7.4] A hipótese da proposição anterior vale para todos os limites de bits suficientemente grandes .a

A prova do teorema acima usa alguns martelos pesados ​​como caixas pretas, mas é elementar (nota: "elementar" " fácil "). Ou seja, ele usa o limite de Milnor-Thom no número de componentes conectados de uma variedade semialgebraica real (o mesmo limite usado por Ben-Or para provar limites mais baixos na distinção / classificação de elementos no modelo de árvore de computação real), a decomposição de Collins ( usado para provar a eliminação eficaz do quantificador em ), um argumento de posição geral e poucas outras idéias. No entanto, todas essas técnicas dependiam apenas do grau dos polinômios envolvidos e, portanto, não podem ser usadas para provar como na proposição acima (de fato, [1, Prop. 7.5] constrói um polinômioR PN C g det g detRPNCg do mesmo grau que modo que a proposição acima falhe com no lugar de ). Analisar essa situação e procurar propriedades que ultrapassaram os graus foi uma das inspirações para o TCG.detgdet

[1] K. Mulmuley. Limites inferiores em um modelo paralelo sem operações de bit . SIAM J. Comput., 28 (4), 1460–1509, 1999

Joshua Grochow
fonte
8

Isso fez o meu dia quando meu amigo James me disse que esse tópico de muito tempo atrás foi reavivado. Obrigado por isso.

Além disso, tive o desejo de compartilhar algumas referências interessantes que são relevantes para L vs Log (DCFL) vs Log (CFL). Tenha um ótimo dia!

http://link.springer.com/chapter/10.1007%2F978-3-642-14031-0_35#page-1

http://link.springer.com/chapter/10.1007/3-540-10003-2_89?no-access=true

http://link.springer.com/chapter/10.1007%2F978-3-642-00982-2_42#page-1

http://www.researchgate.net/publication/220115950_A_Hardest_Language_Recognized_by_Two-Way_Nondeterministic_Pushdown_Automata

Michael Wehar
fonte
7

este novo artigo foi destacado apenas por Luca Aceto em seu blog como um melhor artigo do EATCS na ICALP 2014 e tem uma nova maneira de separar NL / P:

  • Resultados de dureza para Wehar de não-vazio de interseção

    Reexaminamos cuidadosamente uma construção de Karakostas, Lipton e Viglas (2003) para mostrar que o problema de não vazio de interseção dos DFA (autômatos finitos determinísticos) caracteriza a classe de complexidade NL. Em particular, se restrito a um alfabeto de fita de trabalho binário, existem constantes e modo que, para cada interseção não vazio para DFA é solucionável no espaço , mas não é solucionável em espaço. Otimizamos a construção para mostrar que um número arbitrário de não-vazio de interseção do DFA não pode ser solucionado emc 2 k k c 1 k log ( n ) c 2 k log ( n ) o ( nc1c2kkc1klog(n)c2klog(n)f(k)=o(k)kknf(k)ckknco(nlog(n)log(log(n)))espaço. Além disso, se existe uma função tal que, para cada interseção não vazio de DFA é solucionável em tempo, então P ≠ NL. Se não existe uma constante tal que, para cada interseção , o vazio para DFAs seja solucionável em tempo , então P não contém nenhuma classe de complexidade de espaço maior que NL.f(k)=o(k)kknf(k)ckknc

vzn
fonte