NC = P consecuencias?

35

Complexity Zoo señala en la entrada de EXP que si L = P, entonces PSPACE = EXP. Dado que NPSPACE = PSPACE de Savitch, por lo que puedo decir, el argumento de relleno subyacente se extiende para mostrar que ( NL = P ) ( PSPACE = EXP ) .

(NL=P)(PSPACE=EXP).
También sabemos que L NL NC P a través de la jerarquía alterna limitada por recursos de Ruzzo.

Si NC = P, ¿se sigue que PSPACE = EXP?

Una interpretación diferente de la pregunta, en el espíritu de Richard Lipton: ¿es más probable que algunos problemas en P no puedan ser paralelizados, que ningún procedimiento de tiempo exponencial requiere más que un espacio polinómico?

También estaría interesado en otras consecuencias "sorprendentes" de NC = P (cuanto más improbable, mejor).

Editar: la respuesta de Ryan lleva a otra pregunta: ¿cuál es la hipótesis más débil que se sabe que garantiza PSPACE = EXP?

  • W. Savitch. Relaciones entre complejidades de cinta no deterministas y deterministas, Journal of Computer and System Sciences 4 (2): 177-192, 1970.
  • WL Ruzzo. Sobre la complejidad del circuito uniforme, Journal of Computer and System Sciences 22 (3): 365-383, 1971.

Editar (2014): se actualizó el antiguo enlace del zoológico y se agregaron enlaces para todas las demás clases.

András Salamon
fuente
1
Como estoy seguro de que no soy el único que no sabe qué es NC, aquí hay un enlace: en.wikipedia.org/wiki/NC_%28complexity%29
Emil
@Andras: Otra consecuencia que tal vez ya conozcas, pero que aún no se ha mencionado, es que la jerarquía N C colapsaría, ya que P tiene problemas completos en las reducciones L. NCPL
Joshua Grochow

Respuestas:

28

Sí. N C puede verse como la clase de lenguajes reconocidos por las máquinas Turing alternativas que usan el espacio O ( log n ) y el tiempo ( log n ) O ( 1 ) . (Esto fue probado por primera vez por Ruzzo.) P es la clase en la que las máquinas de Turing alternadas usan espacio O ( log n ) pero pueden tomar hasta n O ( 1 ) tiempo. Por brevedad llamemos a estas clases A T I S P [ ( log nNCO(logn)(logn)O(1)PO(logn)nO(1)) O ( 1 ) , log n ] = N C y A S P A C E [ O ( log n ) ] = P .ATISP[(logn)O(1),logn]=NCASPACE[O(logn)]=P

Supongamos que las dos clases son iguales. Reemplazando la n con 2 n en lo anterior (es decir, aplicando lemas de traducción estándar), se obtienen2n

T I M E [ 2 O ( n ) ] = A S P A C E [ O ( n ) ] = A T I S P [ n O ( 1 ) , n ] A T I M E [ n O ( 1 ) ] = P S P A C E .TIME[2O(n)]=ASPACE[O(n)]=ATISP[nO(1),n]ATIME[nO(1)]=PSPACE

Si T I M E [ 2 O ( n ) ] P S P A C E entonces E X P = P S P A C E también, ya que hay E X P -idiomas completos en T I M E [ 2 O ( n ) ] .TIME[2O(n)]PSPACEEXP=PSPACEEXPTIME[2O(n)]

Editar: aunque la respuesta anterior es quizás más educativa, aquí hay un argumento más simple: E X P = P S P A C E ya se deduce de " P está contenido en el espacio polylog" y la traducción estándar. EXP=PSPACEPNote " P está contenida en el espacio polylog" es una hipótesis mucho más débil que N C = P .PNC=P

Más detalles: Dado que las familias de circuitos N C tienen profundidad ( log n ) c para alguna constante, cada familia de circuitos puede evaluarse en el espacio O ( ( log n ) c ) . Por lo tanto, N C c > 0 S P A C E [ ( log n ) c ] . Entonces P = N C implica P c > 0 SNC(logn)cO((logn)c)NCc>0SPACE[(logn)c]P=NCP A C E [ ( log n ) c ] . La aplicación de traducción (en sustitución de n con 2 n ) implica T I M E [ 2 O ( n ) ] P S P A C E . La existencia de unlenguaje completo E X P en T I M E [ 2 O ( n ) ] finaliza el argumento.Pc>0SPACE[(logn)c]n2nTIME[2O(n)]PSPACEEXPTIME[2O(n)]

Actualización: Abordando la pregunta adicional de Andreas, creo que debería ser posible probar algo como: E X P = P S P A C E si para todo c , cada lenguaje polinomialmente escaso en n O ( log c n ) el tiempo se puede resolver en Polylog espacio. (Ser polinomialmente escaso significa que hay a lo sumo p o l y ( n ) cadenas de longitud n en el lenguaje, para todo nEXP=PSPACEcnO(logcn)poly(n)nn.) Si es verdad, la prueba probablemente iría en la línea de Hartmanis, Immerman, y la prueba de que Sewelson N E = E si y sólo si todos los idiomas polinómicamente escasa en N P está contenido en P . (Tenga en cuenta que n O ( log c n ) el tiempo en el espacio de polylog todavía es suficiente para implicar P S P A C E = E X P. )NE=ENPPnO(logcn)PSPACE=EXP

Ryan Williams
fuente
1
Thanks for the nice answer. Dexter Kozen's Theory of Computation has a nice "uniform" notation for Ruzzo's classes on page 69: STA(f,g,h)STA(f,g,h) where ff bounds space, gg bounds time, and hh bounds alternations. Then NC=STA(logn,,(logn)O(1))NC=STA(logn,,(logn)O(1)) while P=STA(logn,,)P=STA(logn,,) which really highlights the construction.
András Salamon
1
Note that I am saying NC=STA(logn,(logn)O(1),)NC=STA(logn,(logn)O(1),) in the above. However I think these are the same. A machine which takes polynomial time and O(logn)O(logn) space but makes only (logn)O(1)(logn)O(1) alternations can be turned into another alternating machine which takes only (logn)O(1)(logn)O(1) time and O(logn)O(logn) space. (The other direction is obvious.) The idea is to insert more alternations so that each polynomial time existential phase and universal phase is "sped up" to run in only (logn)O(1)(logn)O(1) time and O(logn)O(logn) space, along the lines of Savitch's theorem.
Ryan Williams
6
what we need is some kind of greasemonkey script that automatically links something like "\NP" to the entry in the zoo.
Suresh Venkat
12

(I've seen Ryan's answer, but I just wanted to provide another perspective, which was too long to fit into a comment.)

In the L=PPSPACE=EXPL=PPSPACE=EXP proof, all that you need to know about L, informally, is that when blown up by an exponential, L becomes PSPACE. The same proof goes through for NL, because NL blown up by an exponential also becomes PSPACE.

Similarly, when NC is blown up by an exponential, you do get PSPACE. I like to see this in terms of circuits: NC is the class of polynomial size circuits with polylog depth. When blown up, this becomes exponential size circuits with polynomial depth. One can show that this is exactly PSPACE, once the appropriate uniformity conditions are added in. I guess if NC is defined with L-uniformity, then this will get PSPACE-uniformity.

The proof should be easy. In one direction, take a PSPACE-complete problem like TQBF and express the quantifiers using AND and OR gates of exponential size. In the other direction, try traversing the polynomial depth circuit recursively. The stack size will be polynomial, so this can be done in PSPACE.

Finally, I came up with this argument when I saw the question (and before reading Ryan's answer), so there might be bugs. Please point them out.

Robin Kothari
fuente
1
One correction: NC has circuits of polynomial size and polylog depth, but this is still only polynomial depth after translation.
Ryan Williams
@Ryan: You're right. I'll fix that.
Robin Kothari
1

Here's a little more detail from the perspective of simulating time-space bounded Alternating Turing machine.

Suppose that P=NCP=NC.

Since NC=ATISP((log(n))O(1),O(log(n)))NC=ATISP((log(n))O(1),O(log(n))), we get P=ATISP((log(n))O(1),O(log(n))).

P=ATISP((log(n))O(1),O(log(n))).

Now, consider the linear time universal simulation problem LinULinU where we are given an encoding on a Turing machine MM and an input string xx of length nn and we want to know if MM accepts xx in at most nn steps.

We know that LinUPLinUP. Therefore, there exists a constant cc (sufficiently large) such that ()LinUATISP(logc(n),clog(n)).

()LinUATISP(logc(n),clog(n)).

As a result of a padding argument (a little tricky see comments), we have (1)DTIME(n)ATISP(logc(n),clog(n)).

(1)DTIME(n)ATISP(logc(n),clog(n)).

Extending the padding argument, we get (2)DTIME(nk)ATISP(kclogc(n),kclog(n)).

(2)DTIME(nk)ATISP(kclogc(n),kclog(n)).
(3)DTIME(2nk)ATISP(kcnkc,kcnk).
(3)DTIME(2nk)ATISP(kcnkc,kcnk).

Further, there are known results about the simulation of Alternating time-space bounded Turing machines. In particular, we know that ATISP(logc(n),clog(n))DSPACE(O(logc+1(n))).

ATISP(logc(n),clog(n))DSPACE(O(logc+1(n))).

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

(2)DTIME(nk)DSPACE(kc+1logc+1(n))

(2)DTIME(nk)DSPACE(kc+1logc+1(n))
(3)DTIME(2nk)DSPACE(nk(c+1)).
(3)DTIME(2nk)DSPACE(nk(c+1)).

From (3)(3), we would get that EXP=PSPACEEXP=PSPACE.

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

It is important to notice that P=NCP=NC implies ATISP((log(n))O(1),O(log(n)))=ATISP(logc(n),O(log(n)))

ATISP((log(n))O(1),O(log(n)))=ATISP(logc(n),O(log(n)))
for some constant cc.

Any comments or corrections are welcomed. :)

Michael Wehar
fuente
1
@MichaelWehar Do we know NCkPSPACENCkPSPACE at any fixed kk? In particular do we know NC2PSPACENC2PSPACE and therefore NCPSPACENCPSPACE?
T....
1
@MichaelWehar I do not know but I have never seen anywhere that NCPSPACENCPSPACE. In fact a comment in cstheory.stackexchange.com/questions/39046/… says PuniformNC1=PSPACEPuniformNC1=PSPACE is possible. I have posted a clarification query in cstheory.stackexchange.com/questions/40689/…. Do you think you can take a look?
T....
1
@Turbo Thank you very much for the kind reply!! It may depend on the kind of uniform. For example, NC=ATISP((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
1
@Turbo Thank you for the follow-up!! I really think you should read the definition at the bottom of page 370 from: sciencedirect.com/science/article/pii/0022000081900386
Michael Wehar
1
@Turbo Thanks for all of your follow-ups!! I highly recommend that you read the paper that I linked because in it, it says that most of these notions of uniform NCNC are equivalent. The paper however does not consider PP-uniform NCNC which could possibly be different as I have no way of proving that it is the same.
Michael Wehar