NC = P consequências?

O zoológico de complexidade indica na entrada em EXP que, se L = P , PSPACE = EXP. Como NPSPACE = PSPACE da Savitch, até onde eu sei, o argumento de preenchimento subjacente se estende para mostrar que Também sabemos que L NL NC P via hierarquia alternada limitada por recursos de Ruzzo.

(NL = P) \Rightarrow (PSPACE = EXP) .

$(\text{NL} = \text{P}) \Rightarrow (\text{PSPACE} = \text{EXP}).$

\subseteq

$\subseteq$

\subseteq

$\subseteq$

\subseteq

$\subseteq$

Se NC = P, segue-se PSPACE = EXP?

Uma interpretação diferente da questão, no espírito de Richard Lipton: é mais provável que alguns problemas em P não possam ser paralelizados, do que nenhum procedimento de tempo exponencial requer mais que o espaço polinomial?

Eu também estaria interessado em outras consequências "surpreendentes" de NC = P (quanto mais improvável, melhor).

Edit: A resposta de Ryan leva a uma pergunta adicional: qual é a hipótese mais fraca que se sabe garantir PSPACE = EXP?

W. Savitch. Relações entre complexidades de fita não-determinísticas e determinísticas, Journal of Computer and System Sciences 4 (2): 177-192, 1970.
WL Ruzzo. Sobre a complexidade do circuito uniforme, Journal of Computer and System Sciences 22 (3): 365-383, 1971.

Editar (2014): link antigo atualizado do Zoo e links adicionados para todas as outras classes.

cc.complexity-theory conditional-results András Salamon
fonte

Como eu tenho certeza que não sou o único a não saber o que NC é, aqui está um link: en.wikipedia.org/wiki/NC_%28complexity%29

Emil

@ Andras: Uma outra consequência que talvez você já saiba, mas que ainda não foi mencionada, é que a hierarquia

entraria em colapso, pois

tem problemas completos nas reduções em

N C

$\mathsf{NC}$

P

$\mathsf{P}$

L

$\mathsf{L}$

Joshua Grochow

Respostas:

Sim. pode ser visto como a classe de idiomas reconhecida por máquinas de Turing alternadas que usam espaço e . (Isso foi comprovado pela primeira vez por Ruzzo.) é a classe em que as máquinas de Turing alternadas usam espaço , mas podem levar até tempo. Por uma questão de brevidade, vamos chamar essas classes $NC$ $O(\log n)$ $(\log n)^{O(1)}$ $P$ $O(\log n)$ $n^{O(1)}$ e . $ATISP[(\log n)^{O(1)},\log n] = NC$ $ASPACE[O(\log n)] = P$

Suponha que as duas classes sejam iguais. Substituindo por acima (isto é, aplicando lemas de tradução padrão), obtém-se $n$ $2^n$

. $TIME[2^{O(n)}] = ASPACE[O(n)] = ATISP[n^{O(1)}, n] \subseteq ATIME[n^{O(1)}] = PSPACE$

Se então também, uma vez que existem idiomas completos em . $TIME[2^{O(n)}] \subseteq PSPACE$ $EXP = PSPACE$ $EXP$ $TIME[2^{O(n)}]$

Edit: Embora a resposta acima seja talvez mais educativa, aqui está um argumento mais simples: já segue de " está contido no espaço polylog" e tradução padrão. $EXP = PSPACE$ $P$ Nota " está contido no espaço polylog" é uma hipótese muito mais fraco do que o . $P$ $NC = P$

Mais detalhes: Como as famílias de circuitos têm profundidade para alguma constante, cada família de circuitos pode ser avaliada no espaço . Daí . Então implica $NC$ $(\log n)^c$ $O((\log n)^c)$ $NC \subseteq \bigcup_{c > 0} SPACE[(\log n)^c]$ $P = NC$ . Aplicando tradução (substituindo com ) implica . A existência de um língua -completo em termina o argumento. $P \subseteq \bigcup_{c > 0} SPACE[(\log n)^c]$ $n$ $2^n$ $TIME[2^{O(n)}] \subseteq PSPACE$ $EXP$ $TIME[2^{O(n)}]$

Atualização: Respondendo à pergunta adicional de Andreas, acredito que deve ser possível provar algo como: se, para todos os , toda linguagem polinomialmente esparsa em tempo é solucionável em espaço polylog. (Sendo meios polinomialmente esparsos que há, no máximo, cadeias de comprimento da língua, para todos os $EXP=PSPACE$ $c$ $n^{O(\log^c n)}$ $poly(n)$ $n$ $n$ .) Se for verdade, a prova seria provavelmente ir ao longo das linhas de Hartmanis, Immerman, e comprovante de Sewelson que sse todas as línguas polinomialmente escassa em está contido em . (Observe que o tempo no espaço polylog ainda é suficiente para implicar ) $NE = E$ $NP$ $P$ $n^{O(\log^c n)}$ $PSPACE=EXP$

Ryan Williams
fonte

Obrigado pela resposta agradável. Dexter Kozen Teoria da Computação tem uma boa notação de "uniforme" para as classes de RUZZO na página 69:

, onde

espaço limites,

limites de tempo, e

Bounds alternâncias. Então

enquanto

S T A (f, g, h)

$STA(f,g,h)$

f

$f$

g

$g$

h

$h$

NC = S T A (\log n, *, (\log n)^{O (1)})

$\text{NC} = STA(\log n, {*}, (\log n)^{O(1)})$

que realmente destaca a construção.

P = S T A (\log n, *, *)

$\text{P} = STA(\log n, {*}, {*})$

András Salamon

Observe que estou dizendo

acima. No entanto, acho que estes são os mesmos. Uma máquina que ocupa tempo polinomial e espaço

, mas faz apenas

alternações pode ser transformada em outra máquina alternada que usa apenas

N C = S T A (\log n, (\log n)^{O (1)}, *)

$NC = STA(\log n, (\log n)^{O(1)}, *)$

O (\log n)

$O(\log n)$

(\log n)^{O (1)}

$(\log n)^{O(1)}$

tempo e espaço

. (A outra direcção é evidente.) A ideia é a de inserir mais alternâncias de modo a que cada fase existencial tempo polinomial e fase universal é "acelerado" para ser executado em apenas

hora e

espaço , na linha do teorema de Savitch.

(\log n)^{O (1)}

$(\log n)^{O(1)}$

O (\log n)

$O(\log n)$

(\log n)^{O (1)}

$(\log n)^{O(1)}$

O (\log n)

$O(\log n)$

Ryan Williams

o que precisamos é de algum tipo de script greasemonkey que vincule automaticamente algo como "\ NP" à entrada no zoológico.

Suresh Venkat

(Vi a resposta de Ryan, mas só queria fornecer outra perspectiva, que era longa demais para caber em um comentário.)

Na prova , tudo o que você precisa saber sobre L, informalmente, é que, quando explodido por um exponencial, L se torna PSPACE. A mesma prova é válida para NL, porque NL explodido por um exponencial também se torna PSPACE. $L = P \Rightarrow PSPACE = EXP$

Da mesma forma, quando NC é explodido por um exponencial, você obtém o PSPACE. Eu gosto de ver isso em termos de circuitos: NC é a classe de circuitos polinomiais de tamanho com profundidade de polilog. Quando explodido, isso se transforma em circuitos de tamanho exponencial com profundidade polinomial. Pode-se mostrar que esse é exatamente o PSPACE, uma vez que as condições de uniformidade apropriadas sejam adicionadas. Acho que se NC for definido com uniformidade L, isso obterá uniformidade PSPACE.

A prova deve ser fácil. Em uma direção, pegue um problema completo do PSPACE como o TQBF e expresse os quantificadores usando portas AND e OR de tamanho exponencial. Na outra direção, tente atravessar o circuito de profundidade polinomial recursivamente. O tamanho da pilha será polinomial, portanto, isso pode ser feito no PSPACE.

Finalmente, cheguei a esse argumento quando vi a pergunta (e antes de ler a resposta de Ryan), para que houvesse erros. Por favor, aponte-os.

Robin Kothari
fonte

Uma correção: NC possui circuitos de tamanho polinomial e profundidade de polilog, mas ainda é apenas a profundidade polinomial após a tradução.

Ryan Williams

@ Ryan: Você está certo. Eu vou consertar isso.

Robin Kothari

Aqui está um pouco mais detalhadamente da perspectiva da simulação da máquina de Turing Alternada no espaço-tempo.

Suponha-se que . $P = NC$

Como , obtemos $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$

P = A T I S P ((\log (n))^{O (1)}, O (\log (n))) .

$P = ATISP((\log(n))^{O(1)}, O(\log(n))).$

Agora, considere o tempo linear problema de simulação universal , onde nos é dada uma codificação em uma máquina de Turing e um string de entrada de comprimento e queremos saber se aceita em no máximo passos. $LinU$ $M$ $x$ $n$ $M$ $x$ $n$

Sabemos que . Portanto, existe uma constante (suficientemente grande) tal que $LinU \in P$ $c$

(*) L i n U \in A T I S P (\log^{c} (n), c \log (n)) .

$(*) \; LinU \in ATISP(\log^c(n), c\log(n)).$

Como resultado de um argumento de preenchimento (um pouco complicado ver comentários), temos

(1) D T I M E (n) \subseteq A T I S P (\log^{c} (n), c \log (n)) .

$(1) \; DTIME(n) \subseteq ATISP(\log^c(n), c\log(n)).$

Estendendo o argumento de preenchimento, obtemos

(2) D T I M E (n^{k}) \subseteq A T I S P (k^{c} \log^{c} (n), k c \log (n)) .

$(2) \; DTIME(n^k) \subseteq ATISP(k^c\log^c(n), kc\log(n)).$

(3) D T I M E (2^{n^{k}}) \subseteq A T I S P (k^{c} n^{k c}, k c n^{k}) .

$(3) \; DTIME(2^{n^k}) \subseteq ATISP(k^cn^{kc}, kcn^{k}).$

A T I S P (\log^{c} (n), c \log (n)) \subseteq D S P A C E (O (\log^{c + 1} (n))) .

$ATISP(\log^c(n), c\log(n)) \subseteq DSPACE(O(\log^{c+1}(n))).$

Therefore, we (essentially) have the following for all natural numbers $k$ :

(2^{*}) D T I M E (n^{k}) \subseteq D S P A C E (k^{c + 1} \log^{c + 1} (n))

$(2^{*}) \; DTIME(n^k) \subseteq DSPACE(k^{c+1}\log^{c+1}(n))$

(3^{*}) D T I M E (2^{n^{k}}) \subseteq D S P A C E (n^{k (c + 1)}) .

$(3^{*}) \; DTIME(2^{n^k}) \subseteq DSPACE(n^{k(c+1)}).$

From $(3^{*})$ , we would get that $EXP = PSPACE$ .

====================After Thought===================

It is important to notice that $P = NC$ implies

A T I S P ((\log (n))^{O (1)}, O (\log (n))) = A T I S P (\log^{c} (n), O (\log (n)))

$ATISP((\log(n))^{O(1)}, O(\log(n))) = ATISP(\log^c(n), O(\log(n)))$ for some constant

c

$c$ .

Any comments or corrections are welcomed. :)

Michael Wehar
fonte

@MichaelWehar Sabemos

N C^{k} ⊊ P S P A C E

$NC^k\subsetneq PSPACE$ em qualquer fixo

k

$k$ ? Em particular, sabemos

N C^{2} ⊊ P S P A C E

$NC^2\subsetneq PSPACE$ e portanto

N C \neq P S P A C E

$NC\neq PSPACE$ ?

T ....

@MichaelWehar Eu não sei, mas eu nunca vi em qualquer lugar que

N C \neq P S P A C E

$NC\neq PSPACE$ . De fato, um comentário em cstheory.stackexchange.com/questions/39046/… diz

P - u n i f o r m N C^{1} = P S P A C E

$P-uniform NC^1=PSPACE$ é possível. Publiquei uma consulta de esclarecimento em cstheory.stackexchange.com/questions/40689/… . Você acha que pode dar uma olhada?

T ....

@Turbo Thank you very much for the kind reply!! It may depend on the kind of uniform. For example,

N C = A T I S P ((\log (n))^{O (1)}, O (\log (n)))

$NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$ might only hold for Logspace-uniform NC. Let me think about it and get back to you. :)

Michael Wehar

@Turbo Obrigado pelo acompanhamento !! Eu realmente acho que você deve ler a definição na parte inferior da página 370 em: sciencedirect.com/science/article/pii/0022000081900386

Michael Wehar

@ Turbo Obrigado por todos os seus acompanhamentos !! Eu recomendo que você leia o artigo que eu vinculei porque nele, ele diz que a maioria dessas noções de uniforme

N C

$NC$ são equivalentes. O artigo, no entanto, não considera

P

$P$ -uniforme

N C

$NC$ o que poderia ser diferente, pois não tenho como provar que é o mesmo.

Michael Wehar