¿ implica ?

37

Según tengo entendido, el programa de teoría de la complejidad geométrica intenta separar al demostrar que el funcionamiento de una matriz de valores complejos es mucho más difícil de calcular que el determinante.VPVNP

La pregunta que tuve después de hojear los documentos de GCT: ¿Esto implicaría inmediatamente , o es simplemente un paso importante hacia este objetivo?PNP

Benno
fuente
3
AFAIK, el zoológico da toda la información conocida. qwiki.stanford.edu/wiki/Complexity_Zoo:V#vnp
Michaël Cadilhac
La monografía "Completitud y reducción en la teoría de la complejidad algebraica" por Peter Bürgisser (math-www.uni-paderborn.de/agpb/work/habil.ps) puede darle una mejor idea sobre la pregunta.
MCH
Simplemente actualizando la URL de Michaël: complexzoo.uwaterloo.ca/Complexity_Zoo:V#vnp
András Salamon

Respuestas:

27

La respuesta corta es no'. No se conoce tal implicación. Hay dos obstáculos principales: pasar de la complejidad del circuito aritmético a la complejidad booleana (VP ≠ VNP implica P / poly ≠ NP / poly) y luego pasar de la complejidad del circuito booleano (P / poly ≠ NP / poly) a la complejidad uniforme (P ≠ NP ) Ninguno de estos pasos es conocido. Sin embargo, creo que P / poly ≠ NP / poly implica VP ≠ VNP.

Moritz
fuente
44
Su última oración es verdadera: si hay un campo donde VP = VNP entonces P / poly = NP / poly (siga el enlace en el comentario de Cadilhac).
Diego de Estrada
22

Suponiendo la hipótesis de Riemann generalizada (GRH), se conocen las siguientes conexiones bastante fuertes entre y el colapso de la jerarquía polinómica ( P H ):VP=VNPPH

  1. Si VP=VNP (sobre cualquier campo), la jerarquía polinómica se colapsa al segundo nivel;
  2. Si VP=VNPsobre un campo de característica , entonces N C 3 / p o l y = P / p o l y = P H / p o l y ;0NC3/poly=P/poly=PH/poly
  3. Si VP=VNPsobre un campo de característica finita , entonces N C 2 / p o l y = P / p o l y = P H / p o l y .pNC2/poly=P/poly=PH/poly

Estos son resultados de: Peter Burgisser, " La hipótesis de Cook versus Valiant ", Theor. Comp. Sci., 235: 71–88, 2000.

Ver también: Burgisser, " Completitud y reducción en la teoría de la complejidad algebraica ", 1998.

Iddo Tzameret
fuente
1
Creo que quisiste decir que implica el colapso de la jerarquía polinómica, no que V P V N P implica esto. VP=VNPVPVNP
Robin Kothari
15

Te puedo dar una razón de por qué no estructurado de la separación no probaría .PNP

VP y VNP se centran en funciones algebraicas cuyo grado está limitado por un polinomio. Tenga en cuenta que es fácil de calcular en una función algebraica de grado exponencial con un circuito algebraico de tamaño polinómico.

Existe una reducción conocida de 1 profundidad para los circuitos algebraicos: cualquier circuito algebraico de tamaño polinómico que calcule un polinomio de grado puede convertirse en un circuito algebraico de tamaño polinómico y profundidad O ( log d log n ) .dO(logdlogn)

Es posible pensar en como una variante algebraica de N C 2 , demostrando así que V P V N P asciende a probar un equivalente no uniforme algebraica de N C 2# P . Eso no descartaría P = N P , al menos no de inmediato.VPNC2VPVNPNC2#PP=NP

Descargo de responsabilidad : no puedo acceder al documento en este momento y no recuerdo si la reducción funciona en algún campo o solo en los finitos.

1 LG Valiant, S. Skyum, S. Berkowitz, C. Rackoff. Cálculo paralelo rápido de polinomios con pocos procesadores . SIAM J. Comput. 12 (4), págs. 641-644, 1983.

MassimoLauria
fuente
2
¿Es el equivalente algebraico no uniforme de o N C 2# P ? NC2NPNC2#P
Joshua Grochow
VNPNP#P
2
Valiant y col. El resultado funciona para cualquier campo.
Iddo Tzameret