¿ implica ?

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.$VP \neq VNP$

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?$P \neq NP$

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.

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= VNP$${\rm PH}$

1. Si $VP= VNP\,$ (sobre cualquier campo), la jerarquía polinómica se colapsa al segundo nivel;
2. Si $VP=VNP\,$sobre un campo de característica , entonces N C 3 / p o l y = P / p o l y = P H / p o l y ;$0$$\rm{NC}^3/{\rm poly}={\rm P}/{\rm poly} = {\rm PH}/{\rm poly}$
3. Si $VP=VNP\,$sobre 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 .$p$$\rm{NC}^2/{\rm poly}={\rm P}/{\rm poly} = {\rm PH}/{\rm 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.

Te puedo dar una razón de por qué no estructurado de la separación no probaría .$P \ne NP$

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 ) .$d$$O(\log d \log n)$

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.$VP$$NC^2$$VP \ne VNP$$NC^2 \ne \# P$$P = 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.