Est-ce que impliquent ?

Autant que je sache, le programme de théorie de la complexité géométrique tente de séparer en prouvant que le permament d'une matrice à valeurs complexes est beaucoup plus difficile à calculer que le déterminant.$VP \neq VNP$

Après avoir parcouru les documents du GCT, la question que je me posais: cela impliquerait-il immédiatement ou s’agit-il simplement d’une étape majeure dans la réalisation de cet objectif?$P \neq NP$

La réponse courte est non'. Aucune implication de ce type n'est connue. Il existe deux obstacles principaux: passer de la complexité des circuits arithmétiques à la complexité booléenne (VP ≠ VNP implique P / poly ≠ NP / poly) et ensuite de la complexité du circuit booléen (P / poly ≠ NP / poly) à une complexité uniforme (P ≠ NP). ). Aucune de ces étapes n'est connue. Je pense que P / poly ≠ NP / poly implique cependant VP ≠ VNP.

Dans l'hypothèse de l'hypothèse de Riemann généralisée (GRH), les connexions assez fortes suivantes sont connues entre et l'effondrement de la hiérarchie polynomiale ( P H ):$VP= VNP$${\rm PH}$

1. Si $VP= VNP\,$ (sur n'importe quel champ), la hiérarchie polynomiale s'effondre au deuxième niveau;
2. Si $VP=VNP\,$sur un corps de caractéristique , alors 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\,$sur un corps de caractéristique finie , alors 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}$

Voici les résultats de: Peter Burgisser, "Hypothèse de Cook contre Valiant ", Theor. Comp. Sci., 235: 71-88, 2000.

Voir aussi: Burgisser, " Complétude et réduction de la théorie de la complexité algébrique ", 1998.

Je peux vous donner une raison informelle pourquoi la séparation ne serait pas prouver .$P \ne NP$

VP et VNP se concentrent sur des fonctions algébriques dont le degré est limité par un polynôme. Notez qu'il est facile de calculer une fonction algébrique de degré exponentiel avec un circuit algébrique de taille polynomiale.

Il existe une réduction bien connue de la profondeur 1 des circuits algébriques: tout circuit algébrique de taille polynomiale calculant un polynôme de degré peut être transformé en un circuit algébrique de taille polynomiale et de profondeur O ( log d log n ) .$d$$O(\log d \log n)$

Vous pouvez penser à comme une variante algébrique de N C 2 , prouvant ainsi que V P ≠ V N P revient à prouver un équivalent non uniforme algébrique de N C 2 ≠ # P . Cela n'exclurait pas P = N P , du moins pas immédiatement.$VP$$NC^2$$VP \ne VNP$$NC^2 \ne \# P$$P = NP$

Déni de responsabilité : Je ne peux pas accéder au papier pour le moment et je ne me souviens pas si la réduction fonctionne dans un domaine ou dans un domaine fini.

1 LG Valiant, S. Skyum, S. Berkowitz, C. Rackoff. Calcul parallèle rapide de polynômes à l'aide de peu de processeurs . SIAM J. Comput. 12 (4), pages 641 à 644, 1983.