Un résultat de transfert entre modèles de Valiant et BSS

Pascal Koiran  Sylvain Perifel

Le 24 mars 2005

Introduction

— Calcul de suites de polynômes.

— Classes de Valiant : VP et VNP.

— Question ouverte « VP = VNP ? ».

— Plus simple : résultats de transfert (de la forme « si VP = VNP alors P = NP »).

Plan

1. Complexité, Valiant

2. Séparation d’hypersurfaces

3. Tester l’appartenance à une variété complexe 4. Résultat de transfert

Modèle BSS

— Circuits arithmétiques avec tests sur (C, +, ×, =) :

entrées x_{i}, paramètres ∈ C

portes +, ×, tests « = 0 » (réponse 0 ou 1).

— Une famille de circuits (C_{n}) reconnaît un langage X ⊆ ∪_{n}C^{n} : si |x| = n, alors [x ∈ X ssi C_{n}(x) = 1].

— P_{C} : |C_{n}| ≤ p(n)

PAR_{C} : profondeur polynomiale (+ uniformité).

— Remarque : NP_{C} ⊆ PAR_{C}.

Modèle de Valiant

— Circuits arithmétiques sans test sur (C, +, ×, =) :

variables x_{i}, constantes ∈ {−1, 0, 1}

portes +, × ⟶ polynômes ∈ Z[x_{1}, …, x_{n}]

— Une famille de circuits (C_{n}) calcule une famille de polynômes.

— VP : familles de polynômes calculables par circuits de taille polynomiale

VPSPACE : fonction coefficient PSPACE (f_{n}(x̄) = ∑ϵ̄ a(n, ϵ̄)x̄ϵ̄)

(≡ circuits profondeur polynomiale + uniformité).

— Résultat :

VP = VPSPACE ⟹ P_{C} = PAR_{C}

Séparation d’hypersurfaces : problème

— Polynômes f_{1}, …, f_{s} ∈ Z[x_{1}, …, x_{n}].

— Relation x ∼ y ssi ∀i(f_{i}(x) = 0 ⇔ f_{i}(y) = 0).

— Cellule : classe d’équivalence (appartenir aux mêmes hypersurfaces).

— But : algorithme avec tests VPSPACE, à sorties booléennes, tel que x ≁ y ⇒ C(x) ≠ C(y)

Séparation d’hypersurfaces : pourquoi ?

— Circuit BSS ⟶ famille de tous les polynômes f_{1}, …, f_{s} qui peuvent être calculés lors de l’exécution du circuit — x ∼ y ⇒ C(x) = C(y) (résultats des tests identiques).

— Il suffit de tester si la cellule de x est dans le langage (un s-uple booléen plutôt qu’un n-uple complexe).

Conditions de signe

— Cellule pour f_{1}, …, f_{s} ⟶ condition de signe S ∈ {0, 1}^{s} (2^{s} conditions de signe).

— Condition de signe de x : S_{i} = 1 ssi f_{i}(x) = 0.

— Condition de signe satisfaisable : cs de x pour un certain x ∈ C^{n}.

— Seulement (sd)^{O(n)} cs satisfaisables + algo PSPACE pour les énumérer : a(i, j) = i-ème coordonnée de la j-ème cs satisfaisable.

— But : trouver la condition de signe de l’entrée x ∈ C^{n}.

Algorithme pour la cs

— Sur les cs : ordre total compatible avec l’inclusion.

— S candidat pour x si ∀i, S_{i} = 1 ⇒ f_{i}(x) = 0.

— S_{x} = candidat maximal.

— Recherche dichotomique : tests x ∈ ∪_{i≥k}V_{i} où V_{i} est définie par les f_{j} tels que (S_{i})_{j} = 1.

[figure: S_{x}; 1; 2; 3; 4]

Appartenance à une variété (1)

— V définie par f_{1}, …, f_{s} ∈ Z[x_{1}, …, x_{n}].

— But : pour x ∈ C^{n}, décider si x ∈ V.

— Lemme 1 :

(n + 1) combinaisons linéaires « génériques » des f_{i} définissent V.

— Lemme 2 :

on peut remplacer les éléments transcendants par des entiers croissants suffisamment vite.

— Problème : les coefficients deviennent trop gros. ⟶ réduire le nombre de polynômes étape par étape.

Appartenance à une variété (2)

[figure: \underbrace{f_{1}, …, f_{2(n+1)}}_{V_{1}}; \underbrace{f_{2(n+1)+1}, …, f_{4(n+1)}}_{V_{2}}; …; f_{s}; (n + 1) polynômes; (n + 1) polynômes; (n + 1) polynômes]

Le résultat de transfert

Proposition : Tout A ∈ PAR_{C} est décidé par un algorithme polynomial avec tests VPSPACE. Preuve : soit C le circuit BSS décidant A^{=n}, de profondeur n^{q}.

— Énumération de tous les polynômes rencontrés lors de l’exécution de C.

[figure: n^{q}; s ≤ 2^{n^{q}} ; d ≤ 1; s ≤ 2^{n^{q}−1} ; d ≤ 2; ⋮; s ≤ 1 ; d ≤ 2^{n^{q}}; f_{1}; f_{2}; fs; Nb de cs sat. ≤ (sd)^{O(n)}]

Preuve (suite)

— Ainsi, 2^{n^{O(1)}} polynômes que l’on peut énumérer dans VPSPACE.

— Algorithme de séparation d’hypersurfaces ⟶ S_{x} (la cs de x).

— On « simule » le circuit C grâce aux résultats des tests. □ Corollaire :

VP = VPSPACE ⟹ P_{C} = PAR_{C}

Conclusion

— Résultat clé : peu de cs satisfaisables, on peut les énumérer.

— Peu probable que VP = VPSPACE.

— Et sur (R, +, ×, ≤) ?