Polynômes donnés par des circuits algébriques et généralisation du modèle de Valiant

Sylvain Perifel Stage de DEA avec Pascal Koiran, ENS Lyon Le 30 juin 2004

Table des matières

Introduction 1

1 Une hiérarchie généralisant le modèle de Valiant 4 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Définition de la hiérarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Premières propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.1 Lemmes techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.2 Résultats principaux de stabilité . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4 Polynômes complets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4.1 Stabilité par projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4.2 Des polynômes VΣ^{i}P- et VΠ^{i}P-complets . . . . . . . . . . . . . . . . . . . . 10

1.5 Séparation et effondrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5.1 Propagation d’un effondrement . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5.2 Sur la complexité des fonctions coefficients . . . . . . . . . . . . . . . . . . 13

1.6 Circuit de séparation d’hyperplans . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.6.1 Problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.6.2 Se ramener à des hyperplans vectoriels . . . . . . . . . . . . . . . . . . . . . 16 1.6.3 Le circuit dans le cas d’hyperplans vectoriels . . . . . . . . . . . . . . . . . 16 1.6.4 Conséquences de notre construction . . . . . . . . . . . . . . . . . . . . . . 18

2 Manipulation de polynômes donnés par des circuits 21 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Calcul du degré d’un polynôme dans le cas borné . . . . . . . . . . . . . . . . . . . 22

2.2.1 Calcul des composantes homogènes . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.2 Tester la nullité d’un polynôme . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.4 Borne inférieure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3 Calcul du coefficient d’un monôme . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3.1 Caractéristique nulle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.2 Caractéristique non nulle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.4 Le cas général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4.1 DEG est P-dur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4.2 Relation entre CMN et DEG . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.5 Récapitulatif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Conclusion 29

Bibliographie 30

A Autour de l’hypothèse FPSPACE ⊆ GapP/poly 32 A.1 Une conséquence de FPSPACE ⊆ GapP/poly . . . . . . . . . . . . . . . . . . . . . 32 A.2 Une conséquence de PSPACE ⊆ UP/poly . . . . . . . . . . . . . . . . . . . . . . . 33 A.3 Résumé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Introduction

Les circuits booléens offrent une vision nouvelle de la théorie de la complexité, complétant celle des machines de Turing. Dans le cadre de la complexité algébrique, on définit de manière analogue des circuits algébriques grâce à des portes d’addition et de multiplication. On travaille alors sur un corps K fixé. Les entrées sont des variables x_{i} ou des constantes, et on calcule ainsi des polynômes f ∈ K[x_{1}, …, x_{n}] à plusieurs indéterminées à coefficients dans K.

Plus formellement, un circuit algébrique est un circuit orienté sans cycle, dont les sommets sont de degré entrant 0 ou 2, et dont un et un seul sommet est de degré sortant nul. Ce dernier est appelé sortie ; les sommets de degré entrant nul sont appelés entrées. Les sommets qui ne sont pas des entrées sont appelés portes, et sont étiquetés par + ou ×. Les entrées sont étiquetées par des variables ou des constantes de K. Dans ce qui suit, nous nous autoriserons seulement les constantes −1, 0 et 1.

Le polynôme calculé par la porte d’un circuit est défini de manière naturelle par induction :

– le polynôme calculé par une entrée est son étiquette (une constante ou une variable) ;

– le polynôme calculé par une porte + recevant une flèche des portes α et β est la somme des polynômes calculés par α et β;

– de même, le polynôme calculé par une porte × recevant une flèche des portes α et β est le

produit des polynômes calculés par α et β. Le polynôme calculé par un circuit est le polynôme calculé par sa sortie. La taille d’un circuit algébrique C est notée |C| et représente le nombre de sommets de C.

[figure: x_{1}; ×; ×; x_{2}; x_{3}; −1; 0; 1; +; +; +; +; ×; ×; ×; ×; ×]

Fig. 1 – Un exemple de circuit de taille 16 calculant (de manière compliquée) x_{1}^{4} + x_{2}.

Puisque nous n’autorisons pas d’autres constantes que −1, 0 et 1, les coefficients de nos polynômes resteront dans l’anneau engendré par ces constantes, c’est-à-dire Z dans le cas d’un corps de caractéristique nulle, ou le corps premier Z/pZ dans le cas d’un corps de caractéristique p > 0. Ainsi, nos résultats dépendront souvent de la caractéristique du corps dans lequel on travaille.

Dans ce rapport, nous nous intéressons à deux grandes problématiques sur les circuits algébriques. Dans le premier chapitre, nous les abordons du point de vue de la complexité algébrique : nous définissons une hiérarchie de classes de complexité, décrivons leurs propriétés de base, et étudions les relations entre les classes. Cette hiérarchie s’inspire des classes VP et VNP de Valiant que nous définissons maintenant. Il s’agit de classes de suites de polynômes.

On dit qu’une suite de polynômes (f_{n})_{n∈N} est calculée par la suite de circuits (C_{n})_{n∈N} si pour tout n ≥ 0, f_{n} est calculé par C_{n}. Pour simplifier les notations, on supprimera la référence n ∈ N lorsqu’il n’y a pas d’ambiguïté : ainsi, on écrira (f_{n}) pour la suite (f_{n})_{n∈N}. Selon la tradition informatique, on notera p(n) pour désigner un polynôme en la variable n, plutôt que p seulement. De même, pour les polynômes en plusieurs variables, pour plus de clarté on pourra faire apparaître les variables : (f_{n}(x_{1}, …, x_{p(n)})) plutôt que (f_{n}).

La classe VP ([21]) est l’ensemble des suites de polynômes de degré polynomial calculées par une suite de circuits de taille polynomiale : c’est-à-dire que (f_{n}) ∈ VP si et seulement s’il existe un polynôme p(n) et une suite (C_{n}) de circuits calculant (f_{n}), et vérifiant pour tout n ≥ 0 :

– |C_{n}| ≤ p(n) ;

– le degré de f_{n} est majoré par p(n). Par l’hypothèse sur la taille des circuits, le nombre de variables de f_{n} est majoré par p(n). Intuitivement, VP capture l’ensemble des suites de polynômes «facilement calculables». Valiant autorise en entrée des constantes arbitraires du corps sur lequel on travaille, alors que nous n’autoriserons que −1, 0 et 1.

L’autre classe de Valiant est VNP. Intuitivement, elle capture l’ensemble des suites de polynômes «facilement définissables». On ne sait pas effectuer des sommes sur un nombre exponentiel de termes dans VP, d’où l’idée de permettre ce genre de grosses sommations. Ainsi, par définition une suite (f_{n}(x_{1}, …, x_{u(n)})) est dans VNP s’il existe un polynôme p(n) et une suite (g_{n}(x_{1}, …, x_{u(n)}, y_{1}, …, y_{p(n)})) ∈ VP tels que pour tout n ≥ 0,

f_{n}(x_{1}, …, x_{u(n)}) = ∑_{ϵ̄∈{0,1}^{p(n)}} g_{n}(x_{1}, …, x_{u(n)}, ϵ_{1}, …, ϵ_{p(n)}).

Bien entendu, la question ouverte principale est de savoir si VP = VNP. On pourra consulter [6] ou [15] pour approfondir la théorie de Valiant. L’article original de Valiant est [21].

Dans notre étude, rappelons-le, nous n’autorisons pas les constantes arbitraires, mais seulement −1, 0 et 1. De plus, nous ne nous restreignons pas aux suites de polynômes de degré polynomialement borné. Guillaume Malod, dans sa thèse [15], a déjà étudié les classes de Valiant dans ce contexte : il s’agit des classes VP_{nb}^{0} et VNP_{nb}^{0}, définies de la même façon que précédemment. L’indice signifie «non borné» (pour le degré), et l’exposant 0 signifie «sans constante».

En s’appuyant sur la remarque que dans ces classes, nous ne savons toujours pas calculer les gros produits (par exemple, la factorielle), nous introduisons la hiérarchie des classes VΣ^{i}P et VΠ^{i}P, grâce à des grosses sommes et des gros produits. Nous nous intéressons alors à des problèmes d’effondrement et de séparation de la hiérarchie, puis, grâce à un circuit de séparation d’hyperplans, obtenons un résultat de transfert vers la complexité par machines de Turing algébriques.

Nous espérons que cette hiérarchie puisse créer un cadre propice à l’étude de questions fondamentales faisant intervenir les gros produits, par exemple de savoir si la factorielle est facilement calculable (i.e. s’il existe une constante c telle que pour tout k, il existe un circuit calculant k! de taille ≤ (log k)^{c}). Ou par exemple la τ-conjecture de [3], qui stipule qu’il existe une constante c telle que le nombre de racines entières d’un polynôme f ∈ Z[t] est majoré par (1 + τ(f))^{c}, où τ(f) représente la taille du plus petit circuit calculant f (cette conjecture implique P ≠ NP sur C).

Dans le second chapitre, l’approche est différente. Nous nous penchons cette fois sur la complexité par machine de Turing booléenne de la manipulation de polynômes donnés par des circuits algébriques. En effet, il peut être pratique de coder un polynôme par un circuit algébrique : en quelque sorte, on donne une méthode de calcul du polynôme plutôt que d’expliciter chaque monôme un à un. Si l’on compte utiliser ce codage, il faut être capable de travailler efficacement sur les circuits algébriques. Via deux problèmes, nous montrons que la manipulation n’est pas toujours aisée ; elle dépend notamment du «degré formel complet» du circuit (le degré du polynôme obtenu lorsque l’on remplace les constantes par de nouvelles variables). Par exemple, le calcul du degré d’un polynôme se fait efficacement lorsque le degré formel complet du circuit est polynomial. En revanche, nous ne connaissons pas d’algorithme efficace dans le cas où le degré formel complet est quelconque. Pour le second problème, où il s’agit de calculer le coefficient d’un monôme dans le circuit, on montre une borne inférieure qui élimine l’espoir de résoudre ce problème efficacement.

Avant d’aborder le cœur de notre étude, nous rappelons quelques notions classiques de complexité dont nous nous servons dans ce rapport (voir par exemple [16] ou [8] pour plus de détails).

P (resp. NP) est la classe des problèmes décidables en temps polynomial sur une machine de Turing déterministe (resp. non déterministe). Si L est un langage, on note P^{L} (resp. NP^{L}) la classe des langages reconnus en temps polynomial déterministe (resp. non déterministe) par une machine avec oracle L. De même, si C est une classe de complexité, on note P^{C} (resp. NP^{C}) l’union pour tout L ∈ C des P^{L} (resp. NP^{L}).

On définit par récurrence sur i ≥ 0 les classes Σ_{i}^{p} comme suit : Σ_{0}^{p} = P et Σ_{i+1}^{p} = NP^{Σ_{i}^{p}}. La hiérarchie polynomiale est définie par PH = ∪_{i≥0}Σ_{i}^{p}. La classe PSPACE est l’ensemble des langages décidables en espace polynomial.

La classe UP est l’ensemble des langages reconnus en temps polynomial par machine de Turing ayant au plus un chemin acceptant : L ∈ UP s’il existe A ∈ P et un polynôme p(n) tels que

x ∈ L ⇒ card{y ∈ {0, 1}^{p(|x|)} : (x, y) ∈ A} = 1, et x ∉ L ⇒ card{y ∈ {0, 1}^{p(|x|)} : (x, y) ∈ A} = 0.

La classe ⊕P compte la parité du nombre de chemins acceptants d’une machine non déterministe fonctionnant en temps polynomial : L ∈ ⊕P s’il existe A ∈ P et un polynôme p(n) tels que

x ∈ L ⇔ card{y ∈ {0, 1}^{p(|x|)} : (x, y) ∈ A} impair.

Plus généralement, pour k ≥ 2 on définit la classe Mod_{k}P par l’ensemble des langages L vérifiant

x ∈ L ⇔ card{y ∈ {0, 1}^{p(|x|)} : (x, y) ∈ A} ≢ 0 mod k.

Pour k premier, Mod_{k}P est close par complément ([1]), donc on peut prendre ≡ 0 dans la définition.

Enfin, les classes Co-RP et BPP sont probabilistes. Co-RP est l’ensemble des langages L tels qu’il existe un machine probabiliste qui ne se trompe pas sur les entrées qui sont dans L, et qui a une faible probabilité d’erreur pour celles qui ne sont pas dans L. Formellement, un langage L est dans Co-RP s’il existe A ∈ P et un polynôme p(n) tels que pour tout x ∈ {0, 1}^{∗},

– si x ∈ L, alors card{y ∈ {0, 1}^{p(|x|)} : (x, y) ∈ A} = 0 ;

– si x ∉ L, alors card{y ∈ {0, 1}^{p(|x|)} : (x, y) ∈ A} ≥ 2^{p(|x|)−1}. BPP est défini de la même façon mais on autorise les erreurs des deux côtés :

– si x ∈ L, alors card{y ∈ {0, 1}^{p(|x|)} : (x, y) ∈ A} ≥ 3/4.2^{p(|x|)} ;

– si x ∉ L, alors card{y ∈ {0, 1}^{p(|x|)} : (x, y) ∈ A} ≤ 1/4.2^{p(|x|)}.

Nous aurons aussi besoin de classes de fonctions. FP (resp. FPSPACE) est l’ensemble des fonctions calculables en temps (resp. espace) polynomial. #P est la classe des fonctions qui comptent le nombre de chemins acceptants d’une machine de Turing non déterministe fonctionnant en temps polynomial. Plus formellement, f : {0, 1}^{∗} → N est dans #P s’il existe un langage A ∈ P et un polynôme p(n) tel que

f(x) = card{y ∈ {0, 1}^{p(|x|)} : (x, y) ∈ A}.

GapP est la classe des fonctions de {0, 1}^{∗} dans Z qui sont la différence de deux fonctions #P. On rappelle quelques inclusions (PH ⊆ P^{#P} constitue le théorème de Toda [19]) :

P ⊆ UP ⊆ NP ⊆ PH ⊆ P^{#P} ⊆ PSPACE, et P ⊆ Co-RP ⊆ BPP ⊆ Σ_{2}^{p}.

Enfin, lorsque l’on a une classe de complexité C, on définit sa version non uniforme C/poly comme étant l’ensemble des langages L tels qu’il existe un langage L′ ∈ C et une fonction de conseil u : N → {0, 1}^{∗} (i.e. |u(n)| est polynomialement borné en n) vérifiant : x ∈ L si et seulement si (x, u(|x|)) ∈ L′. On a la même notion pour une classe de fonctions F : une fonction f est dans F/poly s’il existe g ∈ F et une fonction de conseil u telles que f(x) = g(x, u(|x|)).

Rappelons enfin quelques résultats sur le permanent. Le permanent d’une matrice est défini similairement au déterminant, à ceci près qu’on ne prend pas en compte la signature de la permutation. Plus précisément, si M = (m_{i,j}) est une matrice carrée de taille n, on définit

per(M) = ∑_{σ∈S_{n}} ∏_{i=1}^{n} m_{i,σ(i)},

où S_{n} est l’ensemble des permutations de {1, …, n}. Malgré cette ressemblance avec le déterminant, nous ne savons pas calculer le permanent efficacement (alors que le déterminant se calcule en temps polynomial, par exemple par réduction de Gauss). Cette difficulté a été capturée dans le résultat de [22] : le calcul du permanent est #P-complet (même pour les matrices à coefficients dans {0, 1}). De même, pour la notion de complétude que nous verrons dans le premier chapitre, la suite (P_{n}) des permanents de matrices carrées de taille n est VNP-complète.

Chapitre 1

Une hiérarchie généralisant le modèle de Valiant

1.1 Introduction

Dans le cadre de la théorie de Valiant, on s’intéresse aux suites de polynômes «facilement calculables» (classe VP), et «facilement définissables» (classe VNP). La première classe correspond aux suites de polynômes de degré polynomialement borné, calculables par des circuits algébriques de taille polynomiale. Dans la seconde, on s’autorise de sommer un nombre simplement exponentiel de tels polynômes. Dans sa thèse [15], Guillaume Malod étudie les classes analogues sans restriction sur le degré des polynômes. Il étudie également les classes dans lesquelles on ne s’autorise pas de constante arbitraire. Dans ce qui suit, nous nous plaçons dans ce cadre : nous n’autorisons pas de constante arbitraire, et ne faisons aucune restriction sur le degré des polynômes calculés.

La puissance obtenue dans VNP en effectuant des grosses sommes ne permet toutefois pas clairement de calculer la factorielle, par exemple. Cependant, ce calcul apparaît fréquemment dans ce domaine : par exemple, dans [15, section 5.5], ainsi que dans [3] (en lien avec la «τ-conjecture»). Ce problème est étudié dans [13]. On ne sait pas si l’on peut calculer efficacement la factorielle. Il semble alors naturel d’envisager des classes de polynômes définis par de gros produits (plutôt que par de grosses sommes), dans lesquelles (2^{n}!) se calcule facilement. C’est ce qui nous amène à étudier la classe VΠP. De même, on pourrait faire des sommes de produits, des produits de sommes de produits, etc. Ainsi, on définit une hiérarchie. C’est l’objet du début de ce chapitre.

Après avoir vu quelques propriétés élémentaires de clôture de ces classes, nous exhibons des suites de polynômes complètes pour chacune d’elles. Puis nous étudions sous quelles hypothèses ces classes coïncident, ou sont distinctes. Enfin, nous exhibons un circuit de séparation d’hyperplans, avec des portes de tests VΠP. Ces gros produits nous permettent d’effectuer des recherches dichotomiques. Nous en déduisons un résutat de transfert portant sur les classes algébriques P et NP non uniformes (dans le cadre du modèle BSS [5]), sous l’hypothèse que les gros produits sont calculables facilement.

1.2 Définition de la hiérarchie

Nous rappelons la définition ([15]) de la classe VP_{nb}^{0} des suites de polynômes calculables par des circuits de taille polynomiale, sans constante, et de degré quelconque («nb» = non borné) :

1.2.1 Définition La classe VP_{nb}^{0} est l’ensemble des suites de polynômes calculables par des circuits algébriques de taille polynomiale. Les seules constantes autorisées sont −1, 0 et 1.

La classe VP_{nb}^{0} constitue le premier niveau de notre hiérarchie. Nous le désignerons indifféremment par VΣ^{0}P ou VΠ^{0}P. Notons que l’exposant 0 signifie qu’il s’agit du niveau zéro de la hiérarchie, alors que dans le cas de VP_{nb}^{0}, il signale l’absence de constante arbitraire. Pour éviter toute confusion, nous utiliserons de préférence VΣ^{0}P, puis VΠ^{0}P, mais plus VP_{nb}^{0}.

Nous définissons maintenant par récurrence les autres niveaux de la hiérarchie. Pour k > 0, la classe VΣ^{k}P est l’ensemble des suites de polynômes (f_{n}(x_{1}, …, x_{u(n)})) telles qu’il existe une suite de polynômes (g_{n}(x_{1}, …, x_{u(n)}, y_{1}, …, y_{v(n)})) ∈ VΠ^{k−1}P, vérifiant pour tout n :

f_{n}(x_{1}, …, x_{u(n)}) = ∑_{ϵ̄∈{0,1}^{v(n)}} g_{n}(x_{1}, …, x_{u(n)}, ϵ̄).

Les fonctions u(n) et v(n) sont polynomialement bornées.

De manière analogue, la classe VΠ^{k}P est définie par des produits. Plus précisément, pour k > 0 la classe VΠ^{k}P est l’ensemble des suites de polynômes (f_{n}(x_{1}, …, x_{u(n)})) telles qu’il existe une suite de polynômes (g_{n}(x_{1}, …, x_{u(n)}, y_{1}, …, y_{v(n)})) ∈ VΣ^{k−1}P, vérifiant pour tout n :

f_{n}(x_{1}, …, x_{u(n)}) = ∏_{ϵ̄∈{0,1}^{v(n)}} g_{n}(x_{1}, …, x_{u(n)}, ϵ̄).

La classe VΣ^{k}P représente donc les polynômes qui sont une somme, de produit, de somme, etc. (k fois), de polynômes dans VΣ^{0}P. De même, la classe VΠ^{k}P représente les polynômes qui sont un produit, de somme, de produit, etc. (k fois), de polynômes dans VΣ^{0}P. On retrouve l’esprit de la hiérarchie polynomiale en complexité booléenne, où le quantificateur ∃ est remplacé par la somme ∑, et le quantificateur ∀ est remplacé par le produit ∏. Bien entendu, on ne reconnaît pas des langages avec nos circuits algébriques, mais on calcule des polynômes. De manière évidente, on a les inclusions suivantes pour tout i ≥ 0 :

(VΣ^{i}P ∪ VΠ^{i}P) ⊆ VΠ^{i+1}P et (VΣ^{i}P ∪ VΠ^{i}P) ⊆ VΣ^{i+1}P.

Pour plus de lisibilité, on adoptera la notation VΣP et VΠP respectivement pour VΣ^{1}P et VΠ^{1}P. De même, s’il n’y a pas d’ambiguïté, on remplacera souvent ϵ̄ par un entier i (sous-entendu, écrit en binaire), et x̄ par x tout simplement. Les chiffres binaires de i seront notés i_{j} (j ≥ 0). Ainsi, on écrira par exemple

f_{n}(x) = ∑_{i=0}^{2^{p(n)}−1} g_{n}(i, x), à la place de f_{n}(x̄) = ∑_{ϵ̄∈{0,1}^{p(n)}} g_{n}(ϵ̄, x̄).

1.3 Premières propriétés

Nous étudions dans cette partie les propriétés de base des classes VΣ^{k}P et VΠ^{k}P : clôture par produit, somme, etc. Nous commençons par une série de lemmes qui préparent la démonstration de la proposition 1.3.2.1.

1.3.1 Lemmes techniques

Les deux remarques suivantes sont immédiates par définition des classes VΣ^{k}P et VΠ^{k}P.

1.3.1.1 Remarque Soit (f_{n}(i, x)) dans VΣ^{k}P pour un certain k ≥ 1. Soit p(n) un polynôme. Alors la suite constituée des polynômes suivants est dans VΣ^{k}P :

g_{n}(x) = ∑_{i=0}^{2^{p(n)}−1} f_{n}(i, x).

1.3.1.2 Remarque Soit (f_{n}(i, x)) dans VΠ^{k}P pour un certain k ≥ 1. Soit p(n) un polynôme. Alors la suite constituée des polynômes suivants est dans VΠ^{k}P :

g_{n}(x) = ∏_{i=0}^{2^{p(n)}−1} f_{n}(i, x).

Les deux prochains lemmes étudient les propriétés de clôture des classes VΣ^{k}P et VΠ^{k}P par multiplication ou addition avec une fonction VΣ^{0}P. 1.3.1.3 Lemme Pour tout k ≥ 0, et tout (f_{n}) dans VΣ^{0}P, on a :

(i) pour tout (g_{n}) dans VΣ^{k}P, (f_{n}g_{n}) est dans VΣ^{k}P ; (ii) pour tout (g_{n}) dans VΠ^{k}P, (f_{n}g_{n}) est dans VΠ^{k}P.

Preuve Par récurrence. Le résultat est clair pour k = 0. Soit k > 0.

(i) (g_{n}) est dans VΣ^{k}P, donc s’écrit sous la forme g_{n}(x) = ∑_{i=0}^{2^{p(n)}−1} h_{n}(i, x), où (h_{n}) est dans VΠ^{k−1}P. Par induction, ((i, x) ↦ f_{n}(x)h_{n}(i, x)) est dans VΠ^{k−1}P, et

f_{n}g_{n}(x) = ∑_{i=0}^{2^{p(n)}−1} f_{n}(x)h_{n}(i, x),

ce qui conclut. (ii) (g_{n}) est dans VΠ^{k}P, donc s’écrit sous la forme g_{n}(x) = ∏_{i=0}^{2^{p(n)}−1} h_{n}(i, x), où (h_{n}) est dans

VΣ^{k−1}P. On définit

h′_{n}(i, x) = (( ∏_{j=0}^{p(n)−1} i_{j})f_{n}(x) + 1 − ∏_{j=0}^{p(n)−1} i_{j})h_{n}(i, x),

où i_{j} est le j-ème chiffre binaire de i. On a : h′_{n}(i, x) = h_{n}(i, x) lorsque i < 2^{p(n)} − 1, et h′_{n}(i, x) = f_{n}(x)h_{n}(i, x) lorsque i = 2^{p(n)} − 1. Ainsi,

∏_{i=0}^{2^{p(n)}−1} h′_{n}(i, x) = f_{n}(x)g_{n}(x).

De plus, (h′_{n}) est dans VΣ^{k−1}P : en effet, ((∏_{j=0}^{p(n)−1} i_{j})f_{n}(x)+1−∏_{j=0}^{p(n)−1} i_{j}) est dans VΣ^{0}P, et (h_{n}) dans VΣ^{k−1}P, donc par hypothèse d’induction le produit est dans VΣ^{k−1}P.

□

1.3.1.4 Lemme Pour tout k ≥ 0, et tout (f_{n}) dans VΣ^{0}P, on a : (i) pour tout (g_{n}) dans VΣ^{k}P, (f_{n} + g_{n}) est dans VΣ^{k}P ; (ii) pour tout (g_{n}) dans VΠ^{k}P, (f_{n} + g_{n}) est dans VΣ^{k+1}P.

Preuve Par récurrence sur k. Pour k = 0, le résultat est clair. Soit k > 0.

(i) g_{n} s’écrit sous la forme g_{n}(x) = ∑_{i=0}^{2^{p(n)}−1} h_{n}(i, x), avec (h_{n}) dans VΠ^{k−1}P. On pose (pour j ∈ {0, 1}) :

h′_{n}(j, i, x) = jh_{n}(i, x) + (1 − j)( ∏_{k=0}^{p(n)−1} i_{k})f_{n}(x).

Alors h′_{n} vérifie h′_{n}(1, i, x) = h_{n}(i, x) (pour tout i), h′_{n}(0, i, x) = 0 pour i < 2^{p(n)} − 1, et h′_{n}(0, 2^{p(n)} − 1, x) = f_{n}(x). Ainsi,

∑_{j=0}^{1} ∑_{i=0}^{2^{p(n)}−1} h′_{n}(j, i, x) = (f_{n} + g_{n})(x).

De plus, (h′_{n}) est dans VΣ^{k}P : par le lemme 1.3.1.3, (jh_{n}(i, x)) est dans VΠ^{k−1}P, et comme ((1 − j)(∏_{k=0}^{p(n)−1} i_{k})f_{n}(x)) est dans VΣ^{0}P, par induction on conclut que la somme de ces deux termes est dans VΣ^{k}P. Ainsi, (f_{n} + g_{n}) est dans VΣ^{k}P.

(ii) g_{n} s’écrit sous la forme g_{n}(x) = ∏_{i=0}^{2^{p(n)}−1} h_{n}(i, x), avec (h_{n}) dans VΣ^{k−1}P. On pose (pour j ∈ {0, 1}) :

h′_{n}(j, i, x) = jh_{n}(i, x) + (1 − j)[( ∏_{k=0}^{p(n)−1} i_{k})f_{n}(x) + 1 − ( ∏_{k=0}^{p(n)−1} i_{k})].

Alors h′_{n} vérifie h′_{n}(1, i, x) = h_{n}(i, x) (pour tout i), h′_{n}(0, i, x) = 1 pour i < 2^{p(n)} − 1, et

h′_{n}(0, 2^{p(n)} − 1, x) = f_{n}(x). Ainsi,

∑_{j=0}^{1} ∏_{i=0}^{2^{p(n)}−1} h′_{n}(j, i, x) = (f_{n} + g_{n})(x).

De plus, (h′_{n}) est dans VΣ^{k−1}P, puisque par le lemme 1.3.1.3, (jh_{n}(i, x)) est dans VΣ^{k−1}P, et comme ((1 − j)[(∏_{k=0}^{p(n)−1} i_{k})f_{n}(x) + 1 − (∏_{k=0}^{p(n)−1} i_{k})]) est dans VΣ^{0}P, par induction on conclut que la somme de ces deux termes est dans VΣ^{k−1}P. Ainsi, (f_{n}+g_{n}) est dans VΣ^{k+1}P.

□

Les deux lemmes qui suivent permettent de supposer que pour deux fonctions quelconques de VΣ^{k}P (resp. VΠ^{k}P), les sommations (resp. produits) varient sur le même intervalle. En effet, ils affirment que l’on peut augmenter la borne supérieure des sommations (resp. produits), tout en restant dans VΣ^{k}P (resp. VΠ^{k}P). Cela nous servira dans la preuve de la proposition 1.3.2.1.

1.3.1.5 Lemme Soient p et q des polynômes vérifiant p(n) ≤ q(n) pour tout n. Soient k ≥ 1 un entier et (f_{n}) une suite de VΣ^{k}P, qui s’exprime par

f_{n}(x) = ∑_{i=0}^{2^{p(n)}−1} g_{n}(i, x),

où (g_{n}) est dans VΠ^{k−1}P. Alors il existe une suite (h_{n}) de VΠ^{k−1}P telle que

f_{n}(x) = ∑_{i=0}^{2^{q(n)}−1} h_{n}(i, x).

(L’indice i varie maintenant entre 0 et 2^{q(n)} − 1, et plus entre 0 et 2^{p(n)} − 1)

Preuve On définit h_{n} comme suit :

h_{n}(i, x) = ( ∏_{j=p(n)}^{q(n)−1}(1 − i_{j}))g_{n}(i, x),

où i_{j} désigne le j-ème chiffre binaire de i. La fonction h_{n} vérifie alors h_{n}(i, x) = 0 si i ≥ 2^{p(n)},

et h_{n}(i, x) = g_{n}(i, x) sinon, ce qui implique que f_{n}(x) = ∑_{i=0}^{2^{q(n)}−1} h_{n}(i, x). Bien entendu, (h_{n}) est dans VΠ^{k−1}P : on multiplie en effet (∏_{j=p(n)}^{q(n)−1}(1 − i_{j})), de VΣ^{0}P, par (g_{n}), de VΠ^{k−1}P, donc (h_{n}) est dans VΠ^{k−1}P par le lemme 1.3.1.3. □

1.3.1.6 Lemme Soient p et q des polynômes vérifiant p(n) ≤ q(n) pour tout n. Soient k ≥ 1 un entier et (f_{n}) une suite de VΠ^{k}P, qui s’exprime par

f_{n}(x) = ∏_{i=0}^{2^{p(n)}−1} g_{n}(i, x),

où (g_{n}) est dans VΣ^{k−1}P. Alors il existe une suite (h_{n}) de VΣ^{k−1}P telle que

f_{n}(x) = ∏_{i=0}^{2^{q(n)}−1} h_{n}(i, x).

(L’indice i varie maintenant entre 0 et 2^{q(n)} − 1, et plus entre 0 et 2^{p(n)} − 1)

Preuve On définit h_{n} comme suit :

h_{n}(i, x) = ( ∏_{j=p(n)}^{q(n)−1}(1 − i_{j}))g_{n}(i, x) + 1 − ∏_{j=p(n)}^{q(n)−1}(1 − i_{j}),

où i_{j} désigne le j-ème chiffre binaire de i. La fonction h_{n} vérifie alors h_{n}(i, x) = 1 si i ≥ 2^{p(n)},

et h_{n}(i, x) = g_{n}(i, x) sinon, ce qui implique que f_{n}(x) = ∏_{i=0}^{2^{q(n)}−1} h_{n}(i, x). Bien entendu, (h_{n}) est dans VΣ^{k−1}P : en effet, on multiplie (∏_{j=p(n)}^{q(n)−1}(1 − i_{j})), de VΣ^{0}P, par (g_{n}), de VΣ^{k−1}P, ce qui reste VΣ^{k−1}P par le lemme 1.3.1.3 ; puis on ajoute une fonction VΣ^{0}P : on reste dans VΣ^{k−1}P par le lemme 1.3.1.4. D’où le résultat. □

1.3.2 Résultats principaux de stabilité

La proposition suivante résume différentes propriétés de clôture des classes VΣ^{k}P et VΠ^{k}P.

1.3.2.1 Proposition

(i) Pour tout k, la classe VΣ^{k}P est close par :

– addition ;

– multiplication ;

– opposé (x ↦ −x). (ii) En ce qui concerne la classe VΠ^{k}P, pour tout k on a :

– la somme de deux suites VΠ^{k}P est VΣ^{k+1}P ;

– le produit de deux suites VΠ^{k}P est VΠ^{k}P ;

– l’opposé d’une suite VΠ^{k}P est VΠ^{k}P.

Preuve On procède par récurrence sur k. Les résultats sont clairs pour k = 0. Soit k > 0.

(i) Soient (f_{n}) et (g_{n}) des suites de fonctions de VΣ^{k}P. Par le lemme 1.3.1.5, on peut supposer qu’elles s’expriment par

f_{n}(x) = ∑_{i=0}^{2^{p(n)}−1} f′_{n}(i, x) et g_{n}(x) = ∑_{i=0}^{2^{p(n)}−1} g′_{n}(i, x),

pour un certain polynôme p, et (f′_{n}) et (g′_{n}) dans VΠ^{k−1}P.

– Pour l’addition : par récurrence, on sait que (f′_{n} + g′_{n}) est dans VΣ^{k}P (somme de deux suites VΠ^{k−1}P). Donc la suite composée des polynômes suivants est dans VΣ^{k}P :

(f_{n} + g_{n})(x) = ∑_{i=0}^{2^{p(n)}−1}(f′_{n} + g′_{n})(i, x)

– Pour la multiplication : par récurrence, on sait que ((i, j, x) ↦ f′_{n}(i, x)g′_{n}(j, x)) est dans VΠ^{k−1}P (produit de deux suites VΠ^{k−1}P). Or

f_{n}g_{n}(x) = ∑_{i=0}^{2^{p(n)}−1} ∑_{j=0}^{2^{p(n)}−1} f′_{n}(i, x)g′_{n}(j, x),

donc (f_{n}g_{n}) est dans VΣ^{k}P.

– Pour l’opposé : la suite (x ↦ −1) est dans VΣ^{0}P, donc par le lemme 1.3.1.3, (−f_{n}) est

dans VΣ^{k}P. (ii) Soient (f_{n}) et (g_{n}) des suites de fonctions de VΠ^{k}P. Par le lemme 1.3.1.6, on peut supposer

qu’elles s’expriment par

f_{n}(x) = ∏_{i=0}^{2^{p(n)}−1} f′_{n}(i, x) et g_{n}(x) = ∏_{i=0}^{2^{p(n)}−1} g′_{n}(i, x),

pour un certain polynôme p, et (f′_{n}) et (g′_{n}) dans VΣ^{k−1}P.

– Pour l’addition : soit

h′_{n}(j, i, x) = jf′_{n}(i, x) + (1 − j)g′_{n}(i, x),

pour j ∈ {0, 1}. Par le lemme 1.3.1.3, il s’agit d’une somme de deux suites VΣ^{k−1}P. Par induction, (h′_{n}) est donc dans VΣ^{k−1}P, et on a :

(f_{n} + g_{n})(x) = ∑_{j=0}^{1} ∏_{i=0}^{2^{p(n)}−1} h′_{n}(j, i, x),

donc (f_{n} + g_{n}) est dans VΣ^{k+1}P.

– Pour la multiplication : on pose comme précédemment

h′_{n}(j, i, x) = jf′_{n}(i, x) + (1 − j)g′_{n}(i, x).

Alors (h′_{n}) est dans VΣ^{k−1}P, donc la suite des polynômes suivants est dans VΠ^{k}P :

f_{n}g_{n}(x) = ∏_{j=0}^{1} ∏_{i=0}^{2^{p(n)}−1} h′_{n}(j, i, x).

– Pour l’opposé : on applique le lemme 1.3.1.3.

□

Nous voyons donc que les classes ainsi définies vérifient des propriétés naturelles de clôture, mais il faut toutefois être prudent : la somme de deux suites VΠ^{k}P n’est pas clairement dans VΠ^{k}P, mais dans VΣ^{k+1}P.

Nous étudions maintenant l’ensemble sur lequel nous pouvons faire les sommations ou les produits. D’après la définition, il s’agit d’un intervalle de la forme 0 ≤ i < 2^{p(n)}, où p(n) est un polynôme. La proposition suivante permet de considérer des ensembles plus compliqués, c’est-à-dire d’effectuer des sommes (ou des produits) de la forme

∑_{i∈I} f_{n}(i, x)

pour certains ensembles I. Lorsque A est un langage sur Σ = {0, 1}, la notation A^{=m} désigne l’ensemble des mots de A de taille m, i.e. A ∩ Σ^{m}. La proposition suivante est énoncée pour les produits, mais bien sûr elle est aussi vraie pour les sommes.

1.3.2.2 Proposition Soient k > 0, et p(n) un polynôme. Soit (f_{n}(i, x)) une suite de VΣ^{k−1}P, où i, uple de variables, est de taille t_{i}(n) ≤ p(n) (intuitivement, i va correspondre à un mot sur {0, 1}), et x un uple de taille |x| ≤ p(n). Soit A ∈ P/poly un langage. Alors la suite (g_{n}(x)) constituée des polynômes suivants est dans VΠ^{k}P :

g_{n}(x) = ∏_{i∈A^{=t_{i}(n)}} f_{n}(i, x).

Preuve Puisque A ∈ P/poly, il existe une suite (C_{n}) de circuits booléens décidant A, de taille polynomiale. En simulant les opérations booléennes par des polynômes, de manière classique, on obtient une suite de fonctions (c_{n}(i)) dans VΣ^{0}P, où i est de taille n, telle que pour toute entrée booléenne i,

c_{n}(i) = \{ \begin{matrix}0 & si i ∉ A \\ 1 & sinon. \end{matrix}

La suite des fonctions (prenant les mêmes arguments que (f_{n}))

h_{n}(i, x) = c_{t_{i}(n)}(i)f_{n}(i, x) + 1 − c_{t_{i}(n)}(i)

est dans VΣ^{k−1}P par les lemmes 1.3.1.3 et 1.3.1.4 ((c_{t_{i}(n)}) est VΣ^{0}P puisque t_{i}(n) est polynomialement bornée). Donc on a

g_{n}(x) = ∏_{i∈A^{=t_{i}(n)}} f_{n}(i, x) = ∏_{i=0}^{2^{t_{i}(n)}−1} h_{n}(i, x)

et (g_{n}) est VΠ^{k}P. □

1.4 Polynômes complets

Dans cette section, on s’intéresse à des polynômes complets pour les classes que l’on vient de définir. Dans un premier temps, nous montrons qu’elles sont stables par projection, puis nous exhibons un polynôme complet pour chacune d’elles.

1.4.1 Stabilité par projection

On reprend la notion de projection (non bornée) de la thèse de Guillaume Malod :

1.4.1.1 Définition Soient deux suites de polynômes (f_{n}(x_{1}, …, x_{u(n)})) et (g_{n}(y_{1}, …, y_{v(n)})). On dit que (g_{n}) est une projection de (f_{n}) via les fonctions s(n) et t(n) lorsque :

– s(n) et t(n) sont polynomialement bornées ;

– g_{n}(y_{1}, …, y_{v(n)}) = f_{t(n)}(a_{1}, …, a_{u(t(n))}), où a_{i} est soit l’une des variables y_{j}, soit un entier

calculable par un circuit algébrique de taille ≤ s(n) à partir des constantes −1, 0 et 1. On dit que (g_{n}) est une projection de (f_{n}) lorsqu’il existe s(n) et t(n) tels que (g_{n}) est une projection de (f_{n}) via s(n) et t(n).

Montrons que pour tout i, les classes VΣ^{i}P et VΠ^{i}P sont stables par projection. Raisonnons pour cela par récurrence sur i.

Pour i = 0 : soit (g_{n}) une projection de (f_{n}) ∈ VΣ^{0}P, via les fonctions s(n) et t(n). Alors pour tout n, le polynôme g_{n} est obtenu à partir de f_{t(n)} en remplaçant certaines variables par d’autres ou par des entiers relatifs calculables par un circuit de taille inférieure à s(n). Si l’on effectue ces remplacements dans le circuit calculant f_{t(n)}, on obtient un circuit VΣ^{0}P calculant g_{n}.

Pour i > 0, soit (g_{n}) une projection de (f_{n}) ∈ VΣ^{i}P, via les fonctions s(n) et t(n). Puisque (f_{n}) ∈ VΣ^{i}P, le polynôme f_{t(n)} est de la forme

f_{t(n)}(X_{1}, …, X_{u(n)}) = ∑_{ϵ̄∈{0,1}^{v(n)}} f′_{n}(X_{1}, …, X_{u(n)}, ϵ_{1}, …, ϵ_{v(n)})

pour une certaine suite (f′_{n}) de VΠ^{i−1}P. Supposons que g_{n} soit obtenu à partir de f_{t(n)} en remplaçant X_{j} par a_{j}, où a_{j} est soit une variable, soit un entier relatif calculable par un circuit de taille inférieure à s(n). En effectuant les mêmes changements dans les variables X_{j} de f′_{n}, on obtient un polynôme g′_{n} de VΠ^{i−1}P, puisque par récurrence VΠ^{i−1}P est stable par projection. Ainsi, (g_{n}) est dans VΣ^{i}P, ce qui conclut (le cas de VΠ^{i}P est identique).

1.4.2 Des polynômes VΣ^{i}P- et VΠ^{i}P-complets

La notion de projection nous permet de définir une notion de complétude.

1.4.2.1 Définition Soit C une classe de suites de polynômes. On dit qu’une suite (f_{n}) est complète pour C (ou encore C-complète) lorsque les deux conditions suivantes sont vérifiées :

– (f_{n}) ∈ C;

– toute suite (g_{n}) ∈ C est une projection de (f_{n}).

En suivant la technique de la thèse de Guillaume Malod pour VΣP, on va construire des suites de polynômes complètes pour chaque classe VΣ^{i}P et VΠ^{i}P. Rappelons l’expression de (G_{n}(ā, b̄, ȳ)), la suite de polynômes VΣ^{0}P-complète exhibée dans la thèse (notée (G_{n}^{n}) dans celle-ci) : il s’agit de simuler par niveaux un circuit générique. Le premier niveau consiste en les variables et la constante 1 : on définit

G_{−n}^{n} = 1, G_{−n−1}^{n} = x_{1}, …, G_{0}^{n} = x_{n}.

Puis on calcule tous les produits et sommes possibles du niveau l + 1, en ajoutant de nouvelles variables a_{l+1,i} et b_{l+1,i}, par :

G_{l+1}^{n} = ( ∑_{i=−n}^{l} a_{l+1,i}G_{i}^{n}) ( ∑_{i=−n}^{l} b_{l+1,i}G_{i}^{n}) .

On note alors G_{n} = G_{n}^{n}. La suite (G_{n}) est VΣ^{0}P-complète (puisqu’on a simulé un circuit générique) : on pourra en trouver une preuve dans [15].

Dans la notation (G_{n}(ā, b̄, ȳ)), la taille de ȳ est n. Dans la thèse, il est montré que toute suite (f_{n}) de VΣ^{0}P s’écrit sous la forme

f_{n}(x_{1}, …, x_{p(n)}) = G_{q(n)}(ū, v̄, w_{1}, …, w_{q(n)−p(n)}, x_{1}, …, x_{p(n)}),

où les u_{j}, v_{j} et w_{j} ont pour valeur −1, 0, 1 ou 2.

Nous avons ainsi notre suite VΣ^{0}P-complète (et aussi VΠ^{0}P-complète puisque ces deux classes sont les mêmes). Construisons par récurrence une suite de polynômes (CΣ_{n}^{(i)}) qui soit VΣ^{i}Pcomplète, et (CΠ_{n}^{(i)}) qui soit VΠ^{i}P-complète, telle que la propriété précédente (projection par des constantes de {−1, 0, 1, 2}) soit préservée.

Soit i > 0. On suppose que l’on a déjà construit CΣ_{n}^{(i−1)}(ā, ȳ) pour tout n, où la taille de ȳ est n (dans la notation précédente, pour G_{n} on a regroupé ā et b̄ dans un seul ā, en effectuant juste un renommage ; on procèdera de même par la suite).

On pose

CΠ_{n}^{(i)}(ā, c̄, ȳ) = ∏_{k=0}^{n} ∏_{ϵ̄∈{0,1}^{n−k}}(c_{k}CΣ_{n}^{(i−1)}(ā, y_{1}, …, y_{k}, ϵ_{1}, …, ϵ_{n−k}) + 1 − c_{k}),

où c̄ est un n-uplet de nouvelles variables. Le terme à l’intérieur du produit est VΣ^{i−1}P (cf section précédente), donc (CΠ_{n}^{(i)}) est dans VΠ^{i}P.

Si on a une suite VΠ^{i}P dont les éléments sont de la forme

f_{n}(x_{1}, …, x_{p(n)}) = ∏_{ϵ̄} g_{n}(x̄, ϵ̄)

avec (g_{n}) dans VΣ^{i−1}P, alors (g_{n}) est projection de (CΣ_{t(n)}^{(i−1)}) par hypothèse de récurrence : elle s’écrit sous la forme

g_{n}(x_{1}, …, x_{p(n)}, y_{1}, …, y_{q(n)}) = CΣ_{t(n)}^{(i−1)}(ū, v_{1}, …, v_{(t−p−q)(n)}, x̄, ȳ)

où les u_{j} et v_{j} prennent leurs valeurs dans {−1, 0, 1, 2}. Alors f_{n} s’écrit sous la forme

f_{n}(x̄) = CΠ_{t(n)}^{(i)}(ū, c̄, v_{1}, …, v_{(t−p−q)(n)}, x̄, ȳ′),

où ȳ′ prend des valeurs quelconques (cet uple est là pour combler la place qui reste), et c_{t(n)−q(n)} = 1, alors que les autres c_{j} sont nuls. Donc (f_{n}) est une projection de (CΠ_{n}^{(i)}), dont les uples prennent leurs valeurs dans {−1, 0, 1, 2}. On condensera l’écriture en CΠ_{n}^{(i)}(ā, ȳ), c’est-à-dire que c̄ est maintenant compris dans ā. On a ainsi montré que (CΠ_{n}^{(i)}) est VΠ^{i}P-complète.

De même, on définit les polynômes de la suite complète pour VΣ^{i}P par :

CΣ_{n}^{(i)}(ā, c̄, ȳ) = ∑_{k=0}^{n} ∑_{ϵ̄∈{0,1}^{n−k}} c_{k}CΠ_{n}^{(i−1)}(ā, y_{1}, …, y_{k}, ϵ_{1}, …, ϵ_{n−k}),

où c̄ est un n-uplet de nouvelles variables. Le terme à l’intérieur de la somme est VΠ^{i−1}P (cf section précédente), donc (CΣ_{n}^{(i)}) est dans VΣ^{i}P.

On montre de la même façon que (CΣ_{n}^{(i)}) est VΣ^{i}P-complète.

1.5 Séparation et effondrement

Maintenant que nous avons établi les propriétés de base des classes de notre hiérarchie, ainsi que l’existence de suites complètes pour chaque classe, nous sommes en mesure d’étudier des problèmes de séparation ou d’effondrement de la hiérarchie. Nous commençons par un lemme sur l’effondrement de la hiérarchie.

1.5.1 Lemme Si VΠ^{2}P ⊆ VΣP, alors la hiérarchie s’effondre sur VΣP.

Preuve Par récurrence, montrons que VΠ^{i}P ⊆ VΣP et VΣ^{i}P ⊆ VΣP pour tout i. Le résultat est clair pour i = 0. Pour i ≥ 1 : VΣ^{i}P consiste en des sommes de VΠ^{i−1}P, qui par récurrence est inclus dans VΣP.

Or la somme de fonctions VΣP est encore VΣP, d’où le résultat. VΠ^{i}P consiste en des produits de VΣ^{i−1}P, donc par récurrence en des produits de VΣP. Ainsi, VΠ^{i}P ⊆ VΠ^{2}P ⊆ VΣP. □

1.5.2 Remarque De la même façon (mais nous ne nous servirons pas de ce résultat ultérieurement), si VΣP = VΠP = VΣ^{0}P alors la hiérarchie s’effondre sur VΣ^{0}P.

1.5.1 Propagation d’un effondrement

Nous poursuivons notre étude par l’effet de la séparation de deux classes pour les niveaux voisins.

1.5.1.1 Proposition Pour i ≥ 1,

VΣ^{i−1}P ≠ VΣ^{i}P ⇒ VΣ^{i}P ≠ VΠ^{i}P.

Preuve Supposons que nous ayons une suite de polynômes (P_{n}) complète pour VΣ^{i}P, dont tous les éléments soient irréductibles et aient un monôme dont le coefficient est 1. Dans ce cas, si P_{n} s’écrit sous la forme d’un gros produit, tous les termes du produit sont −1 ou 1, sauf l’un d’entre eux qui est P_{n} au signe près. Donc si (P_{n}) ∈ VΠ^{i}P, alors (P_{n}) ∈ VΣ^{i−1}P. Ainsi, si on suppose VΣ^{i}P = VΠ^{i}P, (P_{n}) serait dans VΠ^{i}P, donc dans VΣ^{i−1}P. Puisque la suite (P_{n}) est complète, on aurait VΣ^{i−1}P = VΣ^{i}P, et on a montré la contraposée.

Il ne reste donc plus qu’à exhiber une suite de polynômes (P_{n}) VΣ^{i}P-complète, et dont chaque élément est irréductible et contient un monôme dont le coefficient est 1. Soit (C_{n}(x)) (où x est un uple de variables) une suite VΣ^{i}P-complète quelconque (on peut prendre par exemple la suite (CΣ_{n}^{(i)}) de la section précédente). Pour tout n, on définit D_{n}(x, z) = C_{n}(x) + z, où z est une nouvelle variable.

Nous prétendons que pour tout n, D_{n} est irréductible. En effet, étudions le cas de D_{n} pour un certain n quelconque. Si D_{n} s’écrit D_{n}(x, z) = A(x, z)B(x, z), montrons que A ou B est constant. Puisque D_{n} est de degré 1 en z, on peut supposer que A est de degré 1 en z, et que z n’intervient pas dans B. Ainsi,

C_{n}(x) = D_{n}(x, 0) = A(x, 0)B(x).

Donc B(x) divise C_{n}(x), et D_{n}(x, z) (par hypothèse), donc B(x) divise z. Puisque z n’intervient pas dans B, on en déduit que B est constant. Ainsi, D_{n} est irréductible.

Bien entendu, (D_{n}) ∈ VΣ^{i}P. De plus, (D_{n}) est complète puisqu’il suffit de prendre z = 0 pour retrouver (C_{n}). On a donc trouvé notre suite complète de polynômes irréductibles, dont le monôme z a pour coefficient 1. □

De la même façon, nous avons le résultat suivant, qui a son importance en raison de la complétude de (HC_{n}) pour la classe VNP^{0} (sans constante et de degré polynomialement borné), cf [15]. Le polynôme HC_{n} (le hamiltonien d’une matrice) est défini comme le permanent, mais la somme se fait seulement sur les permutations σ ∈ S_{n} qui sont des cycles de longueur n :

HC_{n}(x_{1,1}, …, x_{1,n}, x_{2,1} …, x_{n,n}) = ∑_{σ} ∏_{i=1}^{n} x_{i,σ(i)}.

Le permanent n’est VNP^{0}-complet qu’en caractéristique différente de 2, c’est pourquoi nous préférons utiliser le hamiltonien, dont la complétude est vraie en toute caractéristique. Nous reviendrons sur ce polynôme au second chapitre.

1.5.1.2 Proposition

(HC_{n}) ∉ VΣ^{0}P ⇒ (HC_{n}) ∉ VΠP

Preuve La preuve repose comme précédemment sur l’irréductibilité du polynôme HC_{n}, que nous allons montrer, et sur le fait que le coefficient de chaque monôme de HC_{n} est 1.

Pour simplifier les notations, on fixe un entier n et on note P = HC_{n}. Supposons que P = AB où A et B sont des polynômes. Si A contient la variable x_{i,j} et B contient x_{i,k} (où i, j et k sont quelconques), alors en écrivant A comme un polynôme en x_{i,j} et B comme un polynôme en x_{i,k}, le produit contient au moins un terme contenant x_{i,j}x_{i,k}. Ce qui est impossible puisque AB = P ne contient pas de tel terme. En raisonnant de même sur x_{j,i} et x_{k,i}, on voit que dès que A contient x_{i,j} il contient toutes les variables de la «ligne» (x_{i,l})_{1≤l≤n} et toutes celles la «colonne» (x_{l,j})_{1≤l≤n}. Il contient donc toutes les variables de la «matrice» (x_{l,m}), et B est une constante. Ainsi, P est irréductible. □

1.5.2 Sur la complexité des fonctions coefficients

Nous nous attachons maintenant aux fonctions coefficient des polynômes des suites de notre hiérarchie, pour en déduire des conditions d’effondrement.

Fonctions coefficients de VΣP

Pour un polynôme p(n), on note ϵ̄ = (ϵ̄_{1}, …, ϵ̄_{p(n)}) un uple d’entiers naturels ϵ̄_{i} codés en binaire. Ces entiers seront les puissances des indéterminées X_{i}.

Puisque le degré d’un polynôme calculé par un circuit de taille polynomiale est au plus simplement exponentiel, il existe un polynôme q(n) tel que chaque entier ϵ̄_{i} est au plus égal à 2^{q(n)}, donc contient un nombre de chiffres binaires inférieur ou égal à q(n). Ainsi, la longueur totale de ϵ̄ est au plus p(n)q(n). Le résultat suivant remonte essentiellement à [21] : c’en est une simple généralisation à notre contexte (degré non polynomialement borné).

1.5.2.1 Proposition Supposons que la fonction f : {0, 1}^{∗} → Z, (ϵ̄, n) ↦ f(ϵ̄, n) soit dans GapP/poly, où n est codé en unaire. Alors la suite des polynômes

ϕ_{n}(X_{1}, …, X_{p(n)}) = ∑_{ϵ̄} f(ϵ̄, n)Xϵ̄_{1} ; 1 ⋯ Xϵ̄_{p(n)} ; p(n)

est dans VΣP.

Preuve Par définition de GapP/poly, il existe une fonction g de GapP et une fonction de conseil u(n) (ne dépendant que de l’entier n, et dont la taille est bornée par un polynôme), telle que g(ϵ̄, n, u(n)) = f(ϵ̄, n). Par définition de GapP, il existe deux fonctions g_{1} et g_{2} de #P telles que g = g_{1} − g_{2}.

Or pour i ∈ {1, 2}, g_{i}(ϵ̄, n, u(n)) = card{x̄ : ϕ_{(ϵ̄,n,u(n))}^{(i)}(x̄) est vraie} pour une certaine formule

booléenne ϕ_{(ϵ̄,n,u(n))}^{(i)}, calculable en temps polynomial à partir de (ϵ̄, n, u(n)) (complétude de #SAT

pour les réductions parsimonieuses). ϕ_{(ϵ̄,n,u(n))}^{(i)}(x̄) peut être aisément calculée par une suite de

polynômes (P_{n}^{(i)}(ϵ̄, x̄)) de VΣ^{0}P, qui prend les mêmes valeurs sur {0, 1}^{∗}. Soit P_{n} = P_{n}^{(1)} − P_{n}^{(2)} : cette suite de polynômes est aussi calculable en taille polynomiale.

Alors g(ϵ̄, n, u(n)) = ∑x̄ P_{n}(ϵ̄, n, x̄), et donc

ϕ_{n}(X_{1}, …, X_{p(n)}) = ∑_{ϵ̄} ∑_{x̄} P_{n}(ϵ̄, n, x̄)Xϵ̄_{1} ; 1 ⋯ Xϵ̄_{p(n)} ; p(n).

Maintenant, l’élévation de chaque variable X_{i} à la puissance ϵ̄_{i} donnée en binaire se fait en taille polynomiale en n (mais pas en degré borné), puisque chaque ϵ̄_{i} a un nombre polynomial de chiffres. En effet, pour calculer Y^{l}, où les chiffres binaires de l sont notés l_{j}, on élève Y successivement au carré, et pour chaque résultat Y^{2^{j}} obtenu, on calcule l_{j}Y^{2^{j}} + 1 − l_{j}. Enfin, on multiplie tous ces résultats, qui valent Y^{2^{j}} si l_{j} vaut 1, et 1 si l_{j} = 0.

Ainsi, la suite à l’intérieur de la double somme est dans VΣ^{0}P, donc (ϕ_{n}) ∈ VΣP. □

Nous en déduisons que l’on peut aussi calculer la fonction coefficient chiffre par chiffre (notons toutefois que dans le corollaire suivant, f ne prend pas nécessairement ses valeurs dans {0, 1}) :

1.5.2.2 Corollaire Supposons que la fonction f : (ϵ̄, i, n) ↦ f(ϵ̄, i, n) soit dans GapP/poly, où n est codé en unaire, et i représente un nombre codé en binaire de taille p(n) pour un certain polynôme p. Alors la suite constituée des polynômes suivants est dans VΣP :

ϕ_{n}(X_{1}, …, X_{p(n)}) = ∑_{ϵ̄}( ∑_{i=0}^{2^{p(n)−1}} f(ϵ̄, i, n)2^{i})Xϵ̄_{1} ; 1 ⋯ Xϵ̄_{p(n)} ; p(n).

Preuve

∑_{ϵ̄}( ∑_{i=0}^{2^{p(n)−1}} f(ϵ̄, i, n)T^{i})Xϵ̄_{1} ; 1 ⋯ Xϵ̄_{p(n)} ; p(n) = ∑_{ϵ̄,i} f(ϵ̄, i, n)T^{i}Xϵ̄_{1} ; 1 ⋯ Xϵ̄_{p(n)} ; p(n),

donc en appliquant la proposition précédente et en évaluant en T = 2, on obtient le résultat. □

Notons qu’en degré polynomialement borné (ce qui, rappelons-le, n’est pas le cadre de notre étude), nous avons la réciproque, c’est-à-dire que la fonction coefficient est dans GapP/poly. On pourra se référer à [15] pour une étude plus complète des fonctions coefficient des classes VP et VNP, en degré borné ou non.

Fonctions coefficients de VΠP

Nous nous intéressons maintenant à calculer les coefficients des polynômes des suites de VΠP. Nous montrons qu’en caractéristique p > 0, la fonction coefficient de tels polynômes est calculable en espace polynomial (la fonction appartient à la classe FPSPACE), de même pour VΠ^{2}P. En caractéristique nulle, le nombre de chiffres peut être exponentiel, donc il faut calculer la fonction coefficient chiffre par chiffre. Ces considérations nous permettent de déduire un effondrement de la hiérarchie sur VΣP sous l’hypothèse FPSPACE ⊆ GapP/poly.

Dans la suite, pour alléger les notations, on écrira X̄ϵ̄ pour Xϵ̄_{1} ; 1 ⋯ Xϵ̄_{p(n)} ; p(n), où ϵ̄ est un uple d’entiers écrits en binaire, comme précédemment. Nous séparons les cas où la caractéristique est nulle, puisque les coefficients peuvent avoir un nombre exponentiel de chiffres. Dans ce cas, nous calculons alors la fonction coefficient chiffre par chiffre.

1.5.2.3 Proposition (i) Sur un corps de caractéristique p > 0, supposons que la suite des polynômes

ϕ_{n}(X̄) = ∏_{η̄} g_{n}(η̄, X̄) = ∑_{ϵ̄} f(ϵ̄, n)X̄ϵ̄

soit dans VΠP, c’est-à-dire (g_{n}) ∈ VΣ^{0}P. Alors f ∈ FPSPACE. (ii) Sur un corps de caractéristique nulle, supposons que la suite des polynômes

ϕ_{n}(X̄) = ∏_{η̄} g_{n}(η̄, X̄) = ∑_{ϵ̄}( ∑_{i=0}^{2^{p(n)}−1} f(ϵ̄, i, n)2^{i})X̄ϵ̄,

où f est à valeurs dans {0, 1}, soit dans VΠP (c’est-à-dire (g_{n}) ∈ VΣ^{0}P). Alors f ∈ FPSPACE.

Preuve

(i) Nous utilisons la caractérisation de FPSPACE en termes de circuits de profondeur polynomiale. Il suffit de montrer que l’on peut calculer chaque terme de ϕ_{n}(X̄) par un circuit booléen de profondeur polynomiale en n (et de taille éventuellement exponentielle). On code chaque terme αX̄ϵ̄ par l’uple (α, ϵ̄_{1}, …, ϵ̄_{n}), où α est un entier relatif codé en binaire. Puisqu’on est en caractéristique positive, la taille de α sera bornée par une constante, et le degré du polynôme étant majoré par 2^{q(n)} pour un certain polynôme q, la taille de ϵ̄_{i} est majorée par q(n). Ainsi, la taille du codage d’un terme est polynomiale en n. Au départ, on calcule les termes de g_{n}(η̄, X̄) en profondeur polynomiale (puisque (g_{n}) ∈ VΣ^{0}P), en parallèle pour chaque η̄. Puis par récurrence, à l’étape i on calcule tous les termes de ∏η̄ g_{n}(η̄, X̄), où la sommation concerne tous les η̄ d’un intervalle de taille 2^{i}, en parallèle. Cela s’effectue en profondeur polynomiale, à partir des produits sur les deux demiintervalles, calculés à l’étape de récurrence précédente : les produits de tous les termes deux à deux s’effectuent en une profondeur logarithmique (la multiplication des coefficients se fait en profondeur constante, et l’addition des puissances requiert une profondeur log(n^{O(1)})), puis les additions des monômes égaux se fait en profondeur polynomiale puisqu’il y a au maximum un nombre simplement exponentiel de termes. Puisqu’il y a un nombre polynomial d’étapes, la fonction f est bien dans FPSPACE.

(ii) Par le même raisonnement, on voit que l’on peut calculer le résultat chiffre par chiffre, tout en restant de profondeur polynomiale.

□

De même, on peut calculer la fonction coefficient des polynômes des suites de VΣP en espace polynomial. En composant avec le résultat précédent, on en déduit que la fonction coefficient des polynômes des suites de VΠ^{2}P est dans FPSPACE.

1.5.2.4 Corollaire Sur un corps de caractéristique quelconque, si FPSPACE ⊆ GapP/poly, alors la hiérarchie s’effondre sur VΣP.

Preuve D’après les résultats précédents sur les fonctions coefficients de VΣP (proposition 1.5.2.1 et corollaire 1.5.2.2), l’hypothèse implique que VΠP ⊆ VΣP. De même, VΠ^{2}P ⊆ VΣP. Par le lemme 1.5.1, la hiérarchie s’effondre alors sur VΣP. □

L’hypothèse FPSPACE ⊆ GapP/poly n’a pas une signification très intuitive. En annexe, nous essayons de mieux comprendre cette hypothèse grâce à des classes de langages plutôt que des classes de fonctions.

1.6 Circuit de séparation d’hyperplans

Dans cette partie, nous nous servons de notre hiérarchie pour construire un circuit de séparation d’hyperplans : grâce à des tests VΠP, on peut séparer des hyperplans affines sur K (un corps quelconque) par des circuits algébriques de taille O(n log N), où n est la dimension de l’espace, et N le nombre d’hyperplans. Ensuite, l’utilisation de vecteurs de coordonnées rationnelles de petite taille nous permettra de montrer un résultat de transfert concernant les versions non-uniformes des classes NP sur (K, +, −, =) et P sur (K, +, −, ×, =), que nous définissons ci-dessous.

Un langage L sur K est un sous-ensemble de K^{∞} = ∪_{n≥0}K^{n} : un mot de longeur n est un uple de n éléments de K. Une machine BSS sur (K, +, −, =) ([5], on pourra aussi se référer au livre [4]) est une machine de Turing qui manipule des éléments de K et est capable de les ajouter ou de les soustraire en une étape. La machine peut également tester l’égalité de deux éléments de K. Sur (K, +, −, ×, =), elle peut en outre multiplier deux éléments en une étape. La classe P_{(K,+,−,×,=)} (resp. NP_{(K,+,−,=)}) est l’ensemble des langages L sur K reconnus par une machine BSS déterministe (resp. non déterministe) sur (K, +, −, ×, =) (resp. (K, +, −, =)) en temps polynomial. La version non uniforme de P_{(K,+,−,×,=)}, notée ℙ_{(K,+,−,×,=)}, est l’ensemble des langages L sur K reconnus par une famille de circuits algébriques de taille polynomiale, munis de portes de test pour l’égalité. On a P_{(K,+,−,×,=)} ⊆ ℙ_{(K,+,−,×,=)}.

1.6.1 Problème

Soit K un corps quelconque. Un hyperplan affine de K^{n} est un ensemble de la forme H = {x ∈ K^{n} : ∑_{i=1}^{n} α_{i}x_{i} = β}, où α_{i} et β sont des constantes fixées de K. Lorsque la constante β est nulle (i.e. lorsque l’hyperplan affine passe par 0), on parlera d’hyperplan vectoriel.

On considère une famille d’hyperplans affines (H_{i}), i ∈ I, de K^{n}. On définit la relation d’équivalence suivante sur K^{n} : x ∼ y si et seulement si ∀i ∈ I, x ∈ H_{i} ⇔ y ∈ H_{i}. Chaque classe d’équivalence pour cette relation est appelée cellule de la famille d’hyperplans affines. Dans ce qui suit, nous travaillerons sur des familles finies, ce qui implique que le nombre de cellules sera fini.

On suppose que pour chaque dimension n, on a une famille H_{n} d’hyperplans affines à séparer. Soit (f_{n}(x_{1}, …, x_{p(n)})) une suite de VΠP. Une famille de circuits sur K^{n} avec tests (f_{n}) est une suite de circuits algébriques (C_{n}), ayant n variables en entrée (en plus des constantes −1, 0 et 1), et munis de portes de tests : l’entrée de telles portes est un uple (a_{1}, …, a_{p(n)}), et leur sortie est 0 si f_{n}(a_{1}, …, a_{p}(n)) = 0, et 1 sinon. La sortie de tels circuits sur l’entrée x ∈ K^{n} est un uple de valeurs de {0, 1}, noté C_{n}(x). La famille de circuits sépare les familles H_{n} si pour tout n, pour tous x, y ∈ K^{n}, si x et y ne sont pas dans la même cellule de H_{n} alors C_{n}(x) ≠ C_{n}(y).

Pour tout n ≥ 0, on appelle (H_{i}^{(n)}) les hyperplans de la famille H_{n}, pour i de 1 à N_{n}. On note respectivement f_{i}^{(n)}(x) = 0 les équations les définissant, où les f_{i}^{(n)} sont affines. On suppose que N_{n} = 2^{n^{O(1)}}, où n est la dimension de l’espace. On suppose que la suite des fonctions ϕ_{n} : (i, x) ↦ f_{i}^{(n)}(x), où i est codé en binaire, est dans VΣ^{0}P (c’est-à-dire calculable par une suite de circuits de taille polynomiale, sans constante arbitraire de K). Nous cherchons une suite de circuits qui sépare nos familles d’hyperplans, et qui soit de taille petite. Si le nombre de cellules est c, une borne inférieure évidente sur la profondeur du circuit est ⌈log c⌉, puisque si l’on déplie le circuit en un arbre binaire, il doit avoir au moins c feuilles.

Dans la première partie, nous montrons comment on peut se ramener aux cas d’hyperplans vectoriels, en travaillant dans une dimension supérieure. Nous construisons ensuite une famille de circuits séparant la famille des (H_{i}) de taille O(n log N), où n est la dimension de l’espace, et N le nombre d’hyperplans de la famille.

On se place maintenant dans une dimension n fixée, mais l’hypothèse que (ϕ_{n}) ∈ VΣ^{0}P fournit l’uniformité de la construction pour tout n.

1.6.2 Se ramener à des hyperplans vectoriels

Supposons que nous sachions résoudre le problème dans le cas d’hyperplans vectoriels, c’està-dire que pour toute famille d’hyperplans vectoriels vérifiant la condition (ϕ_{n}) ∈ VΣ^{0}P, nous sachions construire un circuit la séparant de taille O(n log N).

Nous allons construire un circuit séparant notre famille d’hyperplans affines (H_{i}). Nous définissons d’abord une famille d’hyperplans vectoriels (H′_{i}) de K^{n+1} ainsi : si H_{i} est défini par ∑_{i=1}^{n} α_{i}x_{i} = β, alors H′_{i} est défini par ∑_{i=1}^{n} α_{i}x_{i} − βx_{n+1} = 0. La propriété suivante est alors vérifiée : (x_{1}, …, x_{n}) ∈ H_{i} si et seulement si (x_{1}, …, x_{n}, 1) ∈ H′_{i}. On appelle C′ le circuit que l’on sait construire pour séparer la famille des (H′_{i}).

On appelle C le circuit sur K^{n} obtenu en remplaçant dans C′ la variable x_{n+1} par 1, en particulier chaque test f_{n}(x_{1}, …, x_{n+1}) = 0 est remplacé par f_{n}(x_{1}, …, x_{n}, 1) = 0. Soient x et y deux points de K^{n}. Si x et y ne sont pas dans la même cellule de la famille des H_{i}, par exemple il existe i_{0} tel que x ∈ H_{i_{0}} et y ∉ H_{i_{0}}, alors x′ := (x_{1}, …, x_{n}, 1) ∈ H′_{i_{0}} et y′ := (y_{1}, …, y_{n}, 1) ∉ H′_{i_{0}}, donc C′(x′) ≠ C′(y′), ce qui implique que C(x) ≠ C(y), par définition de C.

Ainsi, C fournit une solution à notre problème. Dans la suite, on supposera donc que l’on a une famille d’hyperplans vectoriels (et pas seulement affines).

1.6.3 Le circuit dans le cas d’hyperplans vectoriels

On se donne donc une famille d’hyperplans vectoriels (H_{i}) de K^{n}, i entier entre 1 et N, définis respectivement par f_{i}(x) = 0, où les f_{i} sont linéaires.

On maintient un espace E qui est le plus petit espace dont on est sûr qu’il contient x. C’est l’intersection de tous les hyperplans qui contiennent x que l’on a trouvés jusqu’à présent. Au départ, E = K^{n}. À chaque étape, on trouve un hyperplan H contenant notre point x, mais dont la trace n’est pas triviale sur E (i.e. E∩H ≠ E). Pour cela, on effectue une recherche dichotomique parmi tous les hyperplans dont la trace sur E n’est pas triviale, afin de trouver le premier contenant x. Ainsi, à chaque étape la dimension diminue de E de 1, donc on localise x en au plus n étapes.

Le circuit de séparation

Si α est un vecteur de K^{n}, on notera H_{α} l’hyperplan défini par ∑ α_{j}x_{j} = 0. On aura besoin du résultat technique suivant.

1.6.3.1 Lemme Soient α^{(1)}, …, α^{(k)} des vecteurs de K^{n} linéairement indépendants. Soit β un autre vecteur. Alors la famille (α^{(1)}, …, α^{(k)}, β) est liée si et seulement si H_{α^{(1)}} ∩…∩H_{α^{(k)}} ⊆ H_{β}.

Preuve Supposons que la famille (α^{(1)}, …, α^{(k)}, β) soit liée. Puisque les vecteurs α^{(1)}, …, α^{(k)} sont linéairement indépendants, il existe γ_{1}, …, γ_{k} des scalaires de K tels que β = ∑_{i=1}^{k} γ_{i}α^{(i)}. Ainsi, si l’on prend x dans H_{α^{(1)}} ∩ … ∩ H_{α^{(k)}}, alors ∑_{j=1}^{n} α_{j}^{(i)}x_{j} = 0 pour tout i, donc

∑_{j=1}^{n} β_{j}x_{j} = ∑_{j=1}^{n} ∑_{i=1}^{k} γ_{i}α_{j}^{(i)}x_{j} = ∑_{i=1}^{k} γ_{i} ∑_{j=1}^{n} α_{j}^{(i)}x_{j} = 0,

d’où l’inclusion.

Réciproquement, soit A la matrice

A = ( α^{(1)} ; ⋮ ; α^{(k)} ; β ) .

Si la famille (α^{(1)}, …, α^{(k)}, β) est libre, alors A est de rang k + 1, donc le système

Ax = ( 0 ⋮ 0 1 )

a une solution x, vérifiant pour tout i, ∑_{j} α_{j}^{(i)}x_{j} = 0, et ∑_{j} β_{j}x_{j} = 1. Ainsi, x ∈ (∩_{i}H_{α^{(i)}})\H_{β}, donc on a montré la réciproque. □

Comme mentionné précédemment, on maintient un espace E localisant x le plus précisément possible avec les informations que nous possédons. Au départ, E = K^{n}, et après l’étape k, E = H_{α^{(1)}} ∩ … ∩ H_{α^{(k)}}, où les α^{(i)} sont linéairement indépendants.

Décrivons maintenant l’étape k + 1. On effectue une recherche dichotomique parmi tous les hyperplans H dont la trace sur E est non triviale (c’est-à-dire E ⊈ H), pour trouver le premier contenant x. Pour cela, si on note I l’ensemble des hyperplans de trace non triviale sur E, on effectue O(log N) produits de la forme

∏_{i∈I,i<j} ϕ_{n}(i, x),

que l’on décrit en détail à la fin de cette section. En effet, ces produits nous permettent de déterminer s’il existe un hyperplan < j, de trace non triviale, et contenant x : si oui, on diminue l’intervalle (on fait le produit sur i < (j+j_{min})/2, où j_{min} est la borne du plus grand intervalle visité jusqu’à présent et contenu dans l’intervalle en cours, avec au départ j_{min} = 0) ; sinon, on agrandit l’intervalle (on fait le produit sur i < (j + j′)/2, où j′ était la borne de l’intervalle précédent). Lorsque l’on a trouvé H = H_{α} qui convient, on est sûr que α est linéairement indépendant des α^{(i)}, d’après le lemme 1.6.3.1.

On renouvelle alors E : maintenant, E = H_{α^{(1)}} ∩ … ∩ H_{α^{(k)}} ∩ H_{α}, et on a fini l’étape k + 1. Si en revanche, on ne trouve aucun hyperplan H convenable, alors on arrête la construction,

et la sortie du circuit est le uple constitué du numéro de chaque hyperplan trouvé (en binaire).

Il reste à montrer que le circuit ainsi construit sépare notre famille d’hyperplans. Soient x et y deux points dans des cellules différentes : par exemple x ∈ H et y ∉ H, pour un certain H. Supposons que C(x) = C(y), et que le processus se soit terminé à l’étape k. Alors il existe une suite d’hyperplans H_{i_{j}}, pour j = 1 à k, contenant x et y. H ne fait pas partie de ces hyperplans, puisque y n’est pas dans H. Pour la même raison, la trace de H n’est pas triviale sur ∩_{j}H_{i_{j}}. Donc le processus ne devrait pas s’arrêter pour x, car l’hyperplan H convient : contradiction.

Produits VΠP pour la recherche dichotomique

Il reste à montrer que l’on peut faire dans VΠP des produits pour la recherche dichotomique de la forme

(j, k, x) ↦ ∏_{i∈I,i<j} ϕ_{n}(i, x),

où j est un entier binaire, et k code en binaire les numéros de tous les hyperplans trouvés jusqu’à présent. j se calcule facilement par le circuit, puisque c’est la borne de la recherche dichotomique. Pour I, la proposition 1.3.2.2 nous permet de conclure : il suffit pour cela de montrer que décider si un hyperplan est de trace non triviale sur E (que l’on connaît grâce à k) est dans P/poly. D’après le lemme 1.6.3.1, c’est un simple calcul de rang, puisque la trace de H_{α} est triviale sur H_{α^{(1)}} ∩ … ∩ H_{α^{(k)}} si et seulement si la famille (α^{(1)}, …, α^{(k)}, α) est liée (en effet, on a pris soin lors de la construction de vérifier que les α^{(i)} étaient toujours indépendants). Cela se fait dans P/poly, par exemple par élimination de Gauss.

1.6.4 Conséquences de notre construction

Soit K un corps de caractéristique nulle. Pour tout langage L dans NP_{(K,+,−,=)}, nous déduisons de notre construction une famille de circuits avec tests VΠP qui reconnaît L.

Nous montrons d’abord des lemmes sur l’existence d’un vecteur à coordonnées rationnelles de petite taille dans chaque cellule d’un arrangement d’hyperplans. Un vecteur à coordonnées rationnelles de taille ≤ k est un vecteur dont chaque coordonnée est un rationnel, de numérateur et dénominateur majorés par 2^{k}. Commençons par calculer la taille de la somme et du produit de rationnels.

1.6.4.1 Lemme Soient α et β deux rationnels de taille t et t′ respectivement. Alors – αβ est de taille ≤ t + t′;

– α + β est de taille ≤ t + t′ + 1. En particulier, si A est une matrice de taille n × m dont tous les coefficients sont des rationnels de taille ≤ t, et si x est un vecteur de taille n dont tous les coefficients sont des rationnels de taille ≤ t′, alors Ax est un vecteur de taille m dont tous les coefficients sont des rationnels de taille ≤ n(t + t′) + n − 1.

Preuve Pour les deux premiers points, on utilise simplement les égalités

\frac{p}{q} \frac{p′}{q′} = \frac{pp′}{qq′} et \frac{p}{q} + \frac{p′}{q′} = \frac{pq′ + p′q}{qq′} .

Pour les produits matrices/vecteurs, chaque coefficient de Ax est la somme de n produits d’un coefficient de A par un coefficient de x. □

On dit que n hyperplans sont indépendants si les n vecteurs les définissant forment une famille libre. On dit qu’une cellule C d’un arrangement d’hyperplans de K^{n} est définie par les m hyperplans indépendants H_{1}, …, H_{m} (avec m ≤ n) si X = {H_{1}, …, H_{m}} est un ensemble maximal pour l’inclusion parmi les ensembles dont les éléments sont des hyperplans indépendants et vérifiant C ⊆ ∩X. En d’autres termes, l’intersection des m hyperplans de X est l’espace défini par les équations f_{i}(x) = 0 de la cellule C (on ne prend pas en compte les inéquations g_{i}(x) ≠ 0). Notons que cela décrit de manière unique notre cellule.

1.6.4.2 Lemme Soit H une famille d’hyperplans de K^{n} dont les coefficients sont des entiers majorés en valeur absolue par k. Alors le vecteur x de coordonnées x_{i} = (k + 1)^{i} (pour i de 1 à n) n’est dans aucun hyperplan de la famille H.

Preuve Soit f(x) = ∑_{i=1}^{n} α_{i}x_{i} l’équation d’un hyperplan de la famille H. On écrit f^{+}(x) = ∑_{i=1}^{n} α_{i}^{+}x_{i} et f^{−}(x) = ∑_{i=1}^{n} α_{i}^{−}x_{i}, où α_{i}^{+} = max(0, α_{i}) et α_{i}^{−} = max(0, −α_{i}). Alors f(x) = 0 équivaut à f^{+}(x) = f^{−}(x), c’est-à-dire (en utilisant l’expression de x) ∑_{i=1}^{n} α_{i}^{+}(k + 1)^{i} = ∑_{i=1}^{n} α_{i}^{−}(k + 1)^{i}. Mais puisque les coefficients α_{i}^{+} et α_{i}^{−} sont tous positifs et bornés par k, par unicité de l’écriture en base (k + 1) on en déduit que f(x) = 0 équivaut à ∀i, α_{i} = 0, donc dans ce cas, H ne serait pas un hyperplan. Ainsi, x n’est dans aucun hyperplan de H. □

1.6.4.3 Lemme Soit H une famille d’hyperplans de K^{n} dont les coefficients des équations sont des entiers majorés en valeur absolue par k. Supposons qu’un circuit booléen de taille t nous fournisse l’équation du i-ème hyperplan de H sur l’entrée binaire i. Alors il existe un circuit de taille polynomiale en n, t et log k, qui sur l’entrée constituée des numéros de m hyperplans indépendants (m ≤ n), retourne un vecteur x vérifiant :

– x est dans la cellule définie par les m hyperplans ;

– x est à coordonnées rationnelles de taille polynomiale en n et log k.

Preuve On appelle E l’intersection des m hyperplans H_{1}, …, H_{m} donnés en entrée, et on appelle f_{i} l’équation de H_{i}. Par pivot de Gauss, on peut se ramener à un système triangulaire équivalent f′_{i}(x) = 0 (1 ≤ i ≤ m), où l’on peut supposer que le coefficient de x_{i} dans f′_{i} est non nul. Les coefficients sont des rationnels de taille polynomiale en ceux des f_{i}.

On va se ramener au cas où E = K^{n−m}. On considère pour cela l’application

\begin{aligned}ϕ : & K^{n−m} & → & K^{n} \\ & (x_{m+1}, …, x_{n}) & ↦ & (x_{1}, …, x_{m}, x_{m+1}, …, x_{n}) \end{aligned}

où les x_{1}, …, x_{m} sont obtenus à partir des x_{m+1}, …, x_{n} grâce aux équations f′_{i}(x) = 0. ϕ est linéaire, et injective puisque l’on a m équations indépendantes pour trouver m points. L’image de ϕ est E, ce qui nous fournit une bijection entre espaces de même dimension. De plus, pour calculer les coefficients de ϕ dans la base canonique, il s’agit de résoudre le système des m équations f′_{i}(x) = 0, donc d’inverser la matrice carrée M de taille m dont les coefficients sont de taille polynomiale en ceux des f_{i}, par hypothèse majorés en valeur absolue par k. Soit k′ un majorant de taille polynomiale des numérateurs et dénominateurs des coefficients des f′_{i}. En se rappelant que l’inverse d’une matrice est donné par le produit de l’inverse du déterminant et de la transposée de la matrice des cofacteurs, on remarque que chaque nouveau coefficient est un rationnel dont le numérateur et le dénominateur est majoré en valeur absolue par (k′\sqrt{n})^{n} (on peut utiliser l’inégalité de Hadamard pour majorer le déterminant de M). Ainsi, les coefficients de ϕ sont des rationnels de taille ≤ n(log k′ + 1/2 log n), donc si l’on applique ϕ à un vecteur de coordonnées rationnelles de taille ≤ r, on obtient un vecteur de coordonnées rationnelles de taille ≤ n^{2}(log k′ + 1/2 log n) + nr + n − 1 (cf lemme 1.6.4.1), c’est-à-dire polynomiale en n, log k et r.

Soit H un hyperplan défini par une équation g(x) = 0 à coefficients entiers majorés en valeur absolue par k. Alors par substitution des variables x_{1}, …, x_{m}, ϕ^{−1}(E ∩H) (dans K^{n−m}) est défini par des équations dont les coefficients sont de taille polynomiale en log k et n. Si on appelle b un entier de taille polynomiale majorant tous ces coefficients (que l’on peut calculer explicitement en temps polynomial grâce à l’expression de ϕ), par le lemme précédent, le vecteur x ∈ K^{n−m} défini par x_{i} = (b + 1)^{i} (pour 1 ≤ i ≤ n − m) n’est dans aucun hyperplan de K^{n−m} dont les coefficients sont des entiers majorés en valeur absolue par b. Ainsi, ϕ(x) est dans notre cellule C, puisqu’il est dans E mais dans aucun autre hyperplan de H de trace non triviale sur E, et ses coordonnées sont des rationnels de taille polynomiale en n et log k.

Cela nous fournit l’existence du point cherché, et la procédure suivante pour le trouver.

– Par m appels au circuit donnant les équations des hyperplans, on connaît les m équations définissant notre cellule.

– Par pivot de Gauss, on se ramène à un système triangulaire f′_{i}(x) = 0 (tel que le coefficient de x_{i} dans la i-ème équation soit non nul).

– On calcule les coefficients de ϕ.

– Trouver un entier b de taille polynomiale majorant les coefficients des ϕ^{−1}(E ∩ H).

– On définit x par x_{i} = (b + 1)^{i} pour i = 1 à m.

– On calcule ϕ(x). Le circuit effectuant ces opérations a une taille polynomiale en n, t et log k. □

Nous présentons maintenant le résultat principal de cette section.

1.6.4.4 Proposition On se place sur un corps K de caractéristique nulle. Pour tout langage L ∈ NP_{(K,+,−,=)}, il existe une suite de circuits de taille polynomiale avec tests dans VΠP qui décide L.

Preuve Soit un langage L ∈ NP_{(K,+,−,=)}. On appelle M la machine BSS non déterministe reconnaissant L en temps polynomial. Par le résultat de [12], dans NP_{(K,+,−,=)} on peut quantifier uniquement sur des uples booléens : il existe un langage A ∈ P_{(K,+,−,=)} et un polynôme p(n) tels que

x ∈ L ⇔ ∃y ∈ {0, 1}^{p(|x|)}(x, y) ∈ A.

Soit x = (x_{1}, …, x_{n}) l’entrée de M. On considère les constantes de K utilisées par M (qui sont en nombre fini constant) comme de nouvelles entrées (i.e. x_{n+1}, …, x_{n+m}). M ne fait que des tests de la forme ∑_{j} α_{j}x_{j} + δ = 0 (puisque l’on ne dispose que de l’addition et de l’égalité), où les coefficients α_{j} et δ sont des entiers dans {−2^{t(n)}, …, 2^{t(n)}} pour un certain polynôme t(n) (on peut prendre pour t(n) le temps mis par M pour reconnaître L). Ainsi, L∩K^{n} est la réunion de cellules de l’arrangement d’hyperplans H_{n} contenant tous les hyperplans de K^{n} dont les coefficients sont des entiers dans {−2^{t(n)}, …, 2^{t(n)}}.

Il existe bien sûr un circuit de taille polynomiale en n qui sur l’entrée binaire i donne l’équation du i-ème hyperplan de H_{n}. Remarquons de plus que la famille d’hyperplans H_{n} nous permet même de construire un circuit booléen de taille polynomiale qui, sur l’entrée (q, l) (où q est un point à coordonnées rationnelles donné en binaire, et l le numéro d’un hyperplan), renvoie 0 si q appartient à l’hyperplan l, et 1 sinon (ou inversement).

Puisque cette famille d’hyperplans vérifie les conditions de notre construction précédente (et même plus), on a une suite de circuits (C_{n}) avec tests dans VΠP, qui sépare H_{n}. Puisque L ∩ K^{n} est l’union de cellules, il suffit maintenant sur l’entrée x de déterminer si la cellule D de x est dans L ou non.

Puisque le circuit de séparation précédent nous donne en sortie le numéro des m hyperplans indépendants définissant D, on peut appliquer le lemme 1.6.4.3 pour trouver un vecteur q à coordonnées rationnelles de taille polynomiale en n et qui est dans la cellule D. Il suffit donc de déterminer s’il existe un uple y ∈ {0, 1}^{p(|x|)} tel que (q, y) ∈ A. Puisque q et y sont codés en binaires et q est un vecteur de coordonnées rationnelles de petite taille, on peut simuler le fonctionnement d’un circuit algébrique reconnaissant A par un circuit booléen B de taille polynomiale. B retourne 0 si (q, y) est dans A, et 1 sinon.

Par un gros produit sur tous les uples y, on peut ainsi tester s’il existe y ∈ {0, 1}^{p(|x|)} vérifiant (q, y) ∈ A, et ainsi résoudre le problème L. □

On en déduit le résultat de transfert suivant.

1.6.4.5 Corollaire Soit K un corps de caractéristique nulle. Si VΠP ⊆ VΣ^{0}P sur K, alors NP_{(K,+,−,=)} ⊆ ℙ_{(K,+,−,×,=)}.

1.6.4.6 Remarque L’hypothèse VΠP ⊆ VΣ^{0}P semble peu probable, car – elle implique que la suite définie par

f_{n}(x) = ∏_{i=0}^{2^{n}−1}(x − i)

est dans VΣ^{0}P. On en déduit que si VΠP ⊆ VΣ^{0}P, alors la τ-conjecture ([3]) est fausse.

– De même, si VΠP ⊆ VΣ^{0}P, alors on calcule dans VΣ^{0}P la suite (k!) pour k exponentiel en n, ce qui implique que la factorielle est facile à calculer.

Chapitre 2

Manipulation de polynômes donnés par des circuits

2.1 Introduction

Dans ce chapitre, nous nous intéressons cette fois à la complexité booléenne de manipuler des polynômes donnés par des circuits. Un circuit algébrique est en effet facilement codable en binaire, puisqu’il suffit de décrire la structure du circuit (les arêtes) et le type des portes (addition, multiplication).

Cette manière de coder un polynôme peut être beacoup plus économique que de décrire chaque monôme : par exemple, le polynôme

(x + y)^{2^{n}}

est défini par un circuit de taille linéaire en n (par élévations au carré successives), mais il contient un nombre exponentiel de monômes. Toutefois, pour que ce codage soit utilisable, il faut être capable de manipuler de tels circuits… et ce n’est pas toujours facile !

Plusieurs travaux dans ce sens ont déjà été effectués : citons par exemple le calcul du PGCD de deux polynômes donnés par des circuits, dans [10]. Nous nous intéressons ici à deux problèmes naturels, CMN (Coefficient de Monôme Nul), et DEG (Degré), que nous décrivons ci-dessous. Nous nous plaçons dans le cadre des circuits algébriques sans constante, sur un corps quelconque.

Lorsque nous avons un circuit, on peut s’intéresser à son degré formel complet (terminologie reprise de [15]), qui intuitivement serait le degré du polynôme calculé si toutes les constantes (−1, 0 et 1) étaient remplacées par des variables. Dans ce cas, il n’y aurait aucune annulation (qui apparaîtrait par exemple lorsque l’on ajoute deux quantités opposées), puisque l’on n’a pas de porte de soustraction dans nos circuits. Formellement, on obtient la définition suivante.

2.1.1 Définition Le degré formel complet d’une porte d’un circuit algébrique est défini par récurrence :

– le degré formel complet d’une constante ou d’une variable est 1 ;

– le degré formel complet d’un porte + est le max des degrés formels complets de ses entrées ;

– le degré formel complet d’un porte × est la somme des degrés formels complets de ses entrées. Le degré formel complet d’un circuit est le degré formel complet de sa porte de sortie. On notera deg_{f}(C) le degré formel complet du circuit C.

Il est facile de calculer le degré formel complet d’un circuit, par induction. Mais il semble beaucoup plus difficile de trouver le degré du polynôme que calcule ce circuit. En effet, comme mentionné précédemment, des annulations de monômes dominants peuvent avoir lieu, par exemple. On notera deg(C) le degré du polynôme calculé par le circuit C. Le problème DEG est le suivant :

DEG = {(C, d) : deg(C) ≤ d}.

Le second problème auquel nous nous intéressons est celui du calcul du coefficient d’un monôme dans un circuit donné. Pour obtenir un problème de décision, sur l’entrée (C, m) nous nous demandons plus exactement si le coefficient du monôme m dans le polynôme calulé par C est nul. La notation coef_{C}(m) désignera ce coefficient. Le problème CMN est le suivant :

CMN = {(C, m) : coef_{C}(m) = 0}.

Rappelons que nous notons |C| la taille du circuit C. Les cas où le degré formel complet du circuit d’entrée est grand (i.e. superpolynomial en |C|) posent en général problème. C’est pourquoi nous étudions dans un premier temps les versions «bornées» de nos problèmes : nous nous fixons un polynôme p(n), et nous intéressons à

DEG_{b} = {(C, d) : deg_{f}(C) ≤ p(|C|) et deg(C) ≤ d}
CMN_{b} = {(C, m) : deg_{f}(C) ≤ p(|C|) et coef_{C}(m) = 0}.

Notre étude dépend alors du polynôme p(n), mais maintenant on sait que le degré formel complet du circuit est polynomial. Si l’on veut éviter de formuler nos problèmes à l’aide d’un polynôme p(n), on peut utiliser par exemple la notion de circuit multiplicativement disjoint définie dans [15] : un circuit multiplicativement disjoint vérifie deg_{f}(C) ≤ |C|, et tout circuit peut être transformé en un circuit multiplicativement disjoint en temps polynomial en deg_{f}(C). On peut ainsi reformuler nos deux problèmes en termes de circuits multiplicativement disjoints : nos problèmes prennent alors en entrée (C, d) ou (C, m), avec C multiplicativement disjoint, et nous n’avons plus besoin du test deg_{f}(C) ≤ p(|C|). Les versions bornées de nos problèmes désignerons indifféremment des entrées de degré formel complet majoré par p(|C|), ou des entrées multiplicativement disjointes.

Nous étudions dans un premier temps le calcul du degré dans la version bornée. Ensuite, nous nous intéressons à CMN, version bornée ou non.

2.2 Calcul du degré d’un polynôme dans le cas borné

Dans cette partie, nous obtenons un algorithme Co-RP pour le problème DEG_{b}.

2.2.1 Calcul des composantes homogènes

On s’occupe d’abord du circuit C afin de séparer toutes les composantes homogènes (qui sont en nombre polynomial, d’après l’hypothèse sur le degré formel complet du circuit). [6, prop. 5.28] et [15, lemme 2] utilisent déjà cette technique pour «tronquer» un polynôme. On remplace chaque porte α du circuit par p(|C|) + 1 portes, numérotées (α_{0}, …, α_{p(|C|)}). La porte α_{i} calculera la composante homogène de degré i de la porte α.

Pour les portes d’entrée de notre circuit C : si la porte α est une variable X, alors les p(|C|)+1 nouvelles portes sont (0, X, 0, …, 0). De même, si la porte α est une constante a, alors les p(|C|)+1 nouvelles portes sont (a, 0, …, 0).

On construit alors inductivement le nouveau circuit comme suit (on a déjà traité le cas des entrées). Supposons que l’on en soit à la porte α, dont les deux entrées sont les portes β et γ. Deux cas se présentent.

– α est une porte +. Alors pour tout i, α_{i} = β_{i} + γ_{i}.

– α est une porte ×. Alors pour tout i,

α_{i} = ∑_{j+k=i} β_{j}γ_{k},

ce qui se calcule grâce à i + 1 portes × supplémentaires, pour les produits, et à i portes d’addition. On ajoute donc 2i portes (sans compter α_{i}) pour calculer α_{i}. Ainsi, en tout, on a ajouté p(|C|)(p(|C|) + 1) portes.

Le nouveau circuit a ainsi une taille ≤ |C|(p(|C|) + p(|C|)(p(|C|) + 1)), qui reste polynomiale.

Par récurrence, on voit que la porte α_{i} calcule la composante homogène de degré i de la porte α. La procédure indiquée ci-dessus pour construire le nouveau circuit est clairement polynomiale. Ainsi, on dispose d’un nouveau circuit calculant séparément chaque composante homogène de notre circuit C de départ. Notons f_{i} la composante homogène de degré i (pour 0 ≤ i ≤ p(|C|)) du polynôme f calculé par le circuit C.

Pour tester si deg(C) ≤ d, il suffit alors de tester si pour tout i > d, f_{i} = 0. Il y a donc un nombre polynomial de test de nullité d’un polynôme à effectuer. Ainsi, pour prouver que DEG ∈ Co-RP, il suffit de montrer que tester la nullité d’un polynôme donné par un circuit se fait dans Co-RP.

2.2.2 Tester la nullité d’un polynôme

C’est un problème classique, qui est traité dans [17] par exemple. Pour tester la nullité d’un polynôme f(x_{1}, …, x_{n}), on choisit des n-uples (a_{1}, …, a_{n}) aléatoirement, parmi un ensemble «assez grand», et on calcule f(a_{1}, …, a_{n}). Si le résultat n’est pas nul, on est sûr que f n’est pas nul ; sinon, on réitère. Si après un certain nombre d’itérations, on n’a trouvé que des zéros de f, alors f est nul avec forte probabilité : formellement, on obtient un algorithme Co-RP.

Lorsque les résultats des calculs risquent de devenir trop grands, à cause d’un degré de polynôme exponentiel, par exemple, il est nécessaire d’effectuer les opérations arithmétiques modulo un nombre premier aléatoire, pour que l’algorithme reste polynomial. Cependant, puisque dans notre cas, le degré formel complet de C est majoré par p(|C|), on peut effectuer les calculs directement : on est sûr que chacun des résultats intermédiaires s’écrira avec un nombre polynomial de bits.

Le seul point à résoudre est comment connaître un ensemble «assez grand» dans notre corps (puisque l’on souhaite choisir des points parmi un ensemble assez grand). En effet, dans le cas d’un corps de caractéristique nulle, cela ne pose pas de problème, mais lorsque l’on a un corps de caractéristique p > 0, puisque l’on ne dispose pas de constante arbitraire, on ne peut a priori accéder qu’au corps premier F_{p}, donc à seulement p éléments. Ce qui n’est pas suffisant. Dans l’article [17], on a besoin d’un ensemble ayant au moins 2deg(f) éléments pour avoir une probabilité d’erreur ≤ 1/2.

Pour palier à cela, on travaille dans une extension de F_{p}, définie par

F_{p^{q}} ≃ F_{p}[X]/(Q),

où Q est un polynôme irréductible de degré q de F_{p}. Le corps F_{p^{q}} ayant p^{q} éléments, il suffit de prendre q assez grand pour que p^{q} ≥ 2deg(f) (c’est-à-dire q de l’ordre de log deg_{f}(C)).

Dans [11, prop. II.1.9], il est expliqué comment effectuer les calculs efficacement dans ce surcorps de F_{p} : il s’agit d’additions et de multiplications de polynômes, suivies d’une division euclidienne par Q. Il ne reste donc plus qu’à trouver un polynôme irréductible de degré q. Pour cela, nous utilisons le corollaire de [11, prop. II.1.8] : pour q premier (ce que nous pouvons supposer sans perte de généralité), la proportion de polynômes unitaires irréductibles de degré q dans F_{p} est ≥ 1/(2q). Ainsi, en choisissant aléatoirement O(q) polynômes unitaires, la probabilité de trouver un polynôme irréductible est grande.

Notons que si Q n’est pas irréductible, on a encore l’implication [si f = 0, alors ∀(a_{1}, …, a_{n}) ∈ (F_{p}[X]/(Q))^{n}, f(a_{1}, …, a_{n}) = 0]. Ainsi, même lorsque le polynôme Q obtenu n’est pas irréductible, en effectuant les calculs dans F_{p}[X]/(Q) on ne risque pas de décréter à tort que f est non nul. Les cas où Q est réductible ne gênent donc pas. Il suffit alors de répéter toute la procédure O(q) fois pour avoir une grande probabilité de tomber sur un polynôme irréductible et pouvoir conclure.^{1}

2.2.3 Conclusion

Pour résumer, voici les opérations qu’effectue notre algorithme Co-RP, sur l’entrée (C, d). On appelle f le polynôme calculé par C.

– Construire le circuit calculant séparément chaque composante homogène de f. On appelle f_{i} la composante de degré i.

– Tester si f_{i} = 0 pour tout i > d. Sinon rejeter.

1Si toutefois l’on souhaite vérifier que Q est irréductible sur F_{p}, il existe un algorithme polynomial pour cela, par exemple l’algorithme de Berlekamp [2]. On pourra se référer à [7, 4.2.1.1] pour une exposition de cet algorithme. Notons également qu’il existe des algorithmes déterministes, polynomiaux en q, pour trouver un polynôme irréductible sur F_{p}, par exemple dans [18].

– Accepter.

Les étapes pour tester si un polynôme f(x_{1}, …, x_{n}) est nul sur un corps de caractéristique nulle sont les suivantes. Notons que dans notre cas, nous pouvons majorer deg(f) par deg_{f}(C).

– Répéter k fois :

– choisir aléatoirement n entiers (a_{1}, …, a_{n}) de valeur absolue ≤ 2deg(f) ;

– calculer f(a_{1}, …, a_{n}).

– Si au cours de la boucle, un des points n’annulait pas f, alors f n’est pas nul ; sinon, décréter

que f est nul. La probabilité de se tromper est ≤ 2^{−k}.

Enfin, si l’on se trouve sur un corps de caractéristique p > 0, les étapes pour tester si un polynôme f(x_{1}, …, x_{n}) est nul sont les suivantes.

– Choisir un nombre premier q tel que p^{q} ≥ 2deg(f).

– Répéter q fois :

– choisir aléatoirement un polynôme unitaire Q ∈ F_{p}[X] de degré q;

– on se place maintenant dans l’anneau F_{p}[X]/(Q) ;

– répéter k fois :

– choisir aléatoirement n points (a_{1}, …, a_{n}),

– calculer f(a_{1}, …, a_{n}) ;

– si au cours de la boucle, un des points n’annulait pas f, alors sortir car f n’est pas nul.

– Si f était nul sur tous les points testés, décréter que f est nul. La probabilité de se tromper est O(2^{−k}).

2.2.3.1 Remarque On pourrait également s’intéresser au problème suivant :

DEG′ = {(C, 1^{d}) : deg(C) ≤ d},

c’est-à-dire que d est écrit en unaire, et on n’a plus de restriction sur C. Dans ce cas, on calcule chaque composante homogène de degré ≤ d séparément, et encore séparément toute «la composante» de degré > d. Il suffit alors de tester la nullité de la dernière «composante» de degré > d. Nous obtenons également un algorithme Co-RP pour ce problème. Notons que dans un corps de caractéristique nulle, il faut faire de l’arithmétique modulaire, car nous n’avons plus de restriction sur le degré du polynôme calculé par C.

2.2.4 Borne inférieure

Bien qu’on ait un algorithme Co-RP pour DEG_{b} (on peut donc considérer ce problème facile), on aimerait obtenir une borne inférieure sur la complexité de ce problème. Nous montrons une borne inférieure linéaire évidente : tout algorithme doit lire le circuit jusqu’au bout pour conclure.

En effet, soit un circuit C calculant un polynôme de degré strictement positif. On appelle C_{+} le circuit C auquel on ajoute 0 au résultat, et C_{×} le circuit C dont le résultat est multiplié par 0. Alors deg(C_{+}) > 0 mais deg(C_{×}) ≤ 0. Cependant, puisque la porte ajoutée est la dernière, tout algorithme correct doit lire le code du circuit jusqu’au bout pour différencier les entrées (C_{+}, 0) de (C_{×}, 0), et prend ainsi un temps (au moins) linéaire.

2.2.4.1 Remarque Dans la version non bornée, on montrera plus loin que DEG est P-dur pour la réduction en espace logarithmique. Ce résulat repose sur une simulation des circuits booléens par des polynômes, ce qui requiert de ne pas borner de degré formel complet des circuits algébriques.

2.3 Calcul du coefficient d’un monôme

Nous étudions maintenant la complexité du problème CMN et de sa version bornée CMN_{b}. Nous montrons que ces deux problèmes sont hors de la hiérarchie polynomiale PH en caractéristique nulle (sauf si celle-ci s’effondre), que CMN_{b} est dans P^{#P}, et que CMN est dans PSPACE. En caractéristique k > 0, nous montrons que ces deux problèmes sont Mod_{k}P-complets.

2.3.1 Caractéristique nulle

Nous travaillons ici sur Z, c’est-à-dire que nous ne faisons pas d’arithmétique modulaire. Notre étude repose en grande partie sur le permanent de matrices à coefficients 0 ou 1, à qui on a dédié la partie 2.3.1. En effet, on montre que CMN_{b} en caractéristique nulle est au moins aussi difficile que savoir si le permanent d’une matrice vaut une certaine valeur v, donc l’étude du permanent nous donnera une borne inférieure sur la complexité de CMN_{b} (et a fortiori de CMN).

Le langage Perm

Soit Perm = {(M, v) : per(M) = v}, où M est une matrice à coefficients dans {0, 1}, et v un entier naturel (ce langage apparaît dans [9]). Rappelons que la fonction qui, à une matrice à coefficients dans {0, 1}, associe son permanent, est #P-complète.

Soit L un langage de P^{#P[1]} (le [1] signifie que la machine de Turing n’effectue qu’un seul appel à l’oracle). Soit T la machine de Turing déterministe fonctionnant en temps polynomial correspondante, qui fait un appel à l’oracle pour calculer le permanent d’une matrice M à coefficients dans {0, 1}. Puisque T fonctionne en temps polynomial, la matrice M dont T demande le permanent a une taille p(n) × p(n), où p est un polynôme en la taille n de l’entrée. Ainsi, le permanent de M est majoré par (p(n))!.

Construisons une nouvelle machine de Turing non déterministe N, avec oracle Perm, qui reconnaît le langage L. N simule T tant que T ne fait pas appel à l’oracle. Puis N devine un entier v entre 0 et 2^{p(n)^{2}} − 1 ≥ (p(n))!, ce qui est possible en temps polynomial puisque p(n)^{2} est polynomial en n. Après ce choix non déterministe, N appelle l’oracle Perm sur l’entrée (M, v). Si la réponse de l’oracle est négative (c’est-à-dire per(M) ≠ v), alors on rejette. Sinon, on a trouvé le permanent de M (per(M) = v) : on simule alors la machine T comme si son oracle avait répondu v comme valeur du permanent de M.

Ainsi, si T accepte, notre nouvelle machine N a exactement un chemin acceptant (celui correspondant à la bonne valeur v pour le permanent) ; sinon notre machine n’a pas de chemin acceptant. Puisque notre machine fonctionne en temps polynomial, on en déduit que notre langage L est dans NP^{Perm}, et même UP^{Perm[1]} : Perm est P^{#P[1]}-dur pour les réductions Turing non-déterministes.

Rappelons maintenant le théorème de Toda ([19]) : PH ⊆ P^{#P[1]}. Ainsi, par ce qui précède, nous avons montré que

PH ⊆ NP^{Perm}.

Cela implique que Perm n’est pas dans la hiérarchie polynomiale PH, sauf si cette dernière s’effondre. En effet, supposons que Perm soit contenu dans Σ_{i}^{p}. Alors Σ_{i+1}^{p} = NP^{Σ_{i}^{p}} contient NP^{Perm}, donc contient PH : la hiérarchie s’effondre.

Note : en particulier, puisque Perm est dans P^{#P[1]}, nous avons le corollaire suivant : si P^{#P[1]} = PH, alors la hiérarchie polynomiale s’effondre.

Le langage CMN

Réduction de Perm Soit une matrice M = (m_{i,j}), pour 1 ≤ i, j ≤ n, et soit un entier v. Considérons le polynôme en les n variables X_{j} (1 ≤ j ≤ n) suivant (qui est classique) :

P_{(M,v)}(X_{1}, …, X_{n}) = ∏_{j=1}^{n}(∑_{i=1}^{n} m_{i,j}X_{i}) − vX_{1} ⋯ X_{n}.

Le coefficient du monôme X_{1} ⋯ X_{n} dans ce polynôme est per(M) − v. En effet, pour chaque permutation σ de {1, …, n}, il sort du produit un terme de la forme ∏_{i} m_{i,σ(i)}, donc en tout, on obtient

(∑_{σ} ∏_{i} m_{i,σ(i)}) − v.

À partir de l’entrée (M, v), on construit facilement en temps polynomial un circuit calculant P_{(M,v)}. Puis tester si le coefficient du monôme X_{1} ⋯ X_{n} est nul fourni la réponse au test per(M) = v. De plus, le degré de ce polynôme est n. Ainsi, Perm est plus facile que CMN_{b} pour la réduction polynomiale many-one.

On en déduit que CMN_{b} n’est pas dans la hiérarchie polynomiale PH, sauf si celle-ci s’effondre. En effet, si CMN_{b} était dans PH, alors Perm serait aussi dans PH (stabilité par réduction manyone), ce qui entraîne, on l’a vu, un effondrement de PH.

Borne supérieure

Version bornée Nous allons maintenant montrer que CMN_{b} est dans P^{#P}. Pour résoudre ce problème, nous suivons encore une fois la thèse de Guillaume Malod. On utilise la version «circuits multiplicativement disjoints» de CMN_{b}.

[15] montre que le coefficient d’un monôme dans le polynôme calculé par le circuit multiplicativement disjoint n’est autre que le nombre de «développements» (sous-circuit représentant un seul monôme, avec coefficient 1) du circuit de départ, et dont les variables sont celles du monôme.

Or vérifier si un sous-circuit est un développement correspondant au monôme concerné, est un problème polynomial. Ainsi, la fonction qui compte le nombre de développements correspondant au monôme concerné est dans #P. Dans P^{#P}, on teste donc si le coefficient est nul ou non. Notons que l’on effectue un seul appel à l’oracle.

Version générale Le problème de cette construction est flagrant : elle ne fonctionne que pour des circuits dont le degré formel complet est borné par un polynôme en la taille du circuit.

On peut toutefois résoudre CMN en toute généralité, en espace polynomial. En effet, on utilise pour cela la caractérisation de PSPACE par des circuits booléens de profondeur polynomiale (mais éventuellement de taille exponentielle).

Grace à un circuit booléen, nous évaluons le polynôme calculé par chaque porte de notre circuit algébrique. Pour cela, nous codons chaque terme par son coefficient, chiffre par chiffre (cela prend au maximum un nombre simplement exponentiel de portes, puique chaque coefficient est ≤ 2^{2^{n}}, où n est la taille du circuit), et par la suite de ses puissances (ce qui prend un nombre polynomial de portes supplémentaires). Multiplier deux termes se fait alors en profondeur polynomiale, ainsi qu’additionner deux termes (profondeur log(2^{n^{O(1)}})).

En profondeur polynomiale, on peut donc calculer chaque chiffre du coefficient du monôme qui nous intéresse. Il suffit alors de tester s’il est nul, en faisant (diviser pour régner) un OU de tous les chiffres. Ainsi, nous avons un algorithme PSPACE permettant de décider si le coefficient du monôme dans le circuit algébrique est nul.

Conclusion

Pour résumer, on a montré que CMN est dans PSPACE, mais la version bornée CMN_{b} est dans P^{#P[1]}. On a également montré que ni CMN ni CMN_{b} ne sont dans la hiérarchie polynomiale, sauf si celle-ci s’effondre.

2.3.2 Caractéristique non nulle

Cette fois, on se place sur un corps de caractéristique k non nulle, c’est-à-dire que nous faisons de l’arithmétique modulo k où k est un nombre premier. Plus précisément, nous nous intéressons au problème

CMN_{k} = {(C, m) : coef_{C}(m) ≡ 0 mod k}.

Dans ce cas, nous verrons que l’on peut tester la nullité du coefficient d’un monôme dans Mod_{k}P. Notons que le permanent se calcule facilement modulo 2 (car alors il coïncide avec le déterminant), donc on ne peut plus utiliser le permanent pour montrer des résultats de complétude, si l’on ne veut pas négliger la caractéristique 2. On prendra plutôt le problème de compter le nombre de circuits hamiltoniens d’un graphe, qui est complet quelque soit la caractéristique.

Algorithme

Nous nous servons de la suite de polynômes (G_{n}) complète pour VΣ^{0}P de [15, chap. 5] (voir la partie 1.4 de ce rapport). Dans sa thèse, Malod a calculé les coefficients des monômes de G_{n}. Pour cela, il construit un graphe orienté associé au monôme à étudier, et exprime le coefficient du monôme en fonction du nombre d’arêtes gauches et droites allant du sommet i au sommet j (A_{i,j} et B_{i,j} respectivement). On note k_{i} le nombre d’arêtes arrivant au sommet i. Le coefficient du monôme est alors le produits pour i de 1 à n de a_{i}b_{i}, où a_{i} et b_{i} sont de la forme (on utilise la notation anglo-saxone des coefficients binomiaux pour la lisibilité)

a_{i} = ( \begin{matrix}k_{i} \\ A_{i,i−1} \end{matrix} ) ( \begin{matrix}k_{i} − A_{i,i−1} \\ A_{i,i−2} \end{matrix} ) ⋯ ( \begin{matrix}k_{i} − A_{i,i−1} − … − A_{i,−n+1} \\ A_{i,−n} \end{matrix} )

b_{i} = ( \begin{matrix}k_{i} \\ B_{i,i−1} \end{matrix} ) ( \begin{matrix}k_{i} − B_{i,i−1} \\ B_{i,i−2} \end{matrix} ) ⋯ ( \begin{matrix}k_{i} − B_{i,i−1} − … − B_{i,−n+1} \\ B_{i,−n} \end{matrix} )

Grâce au résultat d’Édouard Lucas ([14, pp. 229–230]), on peut calculer en temps polynomial les gros coefficients binomiaux modulo k, en décomposant leur composantes en base k :

2.3.2.1 Proposition (Lucas,1878) Soit k un nombre premier. Soient N = ∑_{i=0}^{n} n_{i}k^{i} et M = ∑_{i=0}^{n} m_{i}k^{i} deux entiers décomposés en base k. Alors

( \begin{matrix}N \\ M \end{matrix} ) ≡ ∏_{i=0}^{n} ( \begin{matrix}n_{i} \\ m_{i} \end{matrix} ) mod k.

Ainsi, le coefficient de tout monôme de G_{n} se calcule en temps polynomial modulo k. Il ne reste plus qu’à appliquer ce résultat à tout polynôme de VΣ^{0}P. Puisque (G_{n}) est VΣ^{0}P-complète, le circuit C est obtenu comme la projection de G_{t(|C|)} : C = σ(G_{t(|C|)}). Cette projection σ (qui associe aux variables de G_{t(|C|)} des variables de C ou des constantes de {−1, 0, 1, 2}) se calcule en temps polynomial car (G_{n}) simule une suite de circuits génériques. Si maintenant m est le monôme dont on veut connnaître la nullité du coefficient, on a :

coef_{C}(m) = ∑_{m′,σ(m′)=m} coef_{G_{t(n)}}(m′).

On a vu qu’en temps polynomial, on pouvait calculer coef_{G_{t(n)}}(m′), et aussi déterminer si σ(m′) = m. Ainsi, cette somme est Mod_{k}P, ce qui montre que CMN_{k} ∈ Mod_{k}P.

Borne inférieure

Nous montrons maintenant que CMN_{k} est dur pour Mod_{k}P. Puisque «Circuit Hamiltonien» (la fonction qui compte le nombre de circuits hamiltoniens d’un graphe) est #P-complète pour les réductions parsimonieuses ([23]), elle est aussi complète modulo k, c’est-à-dire que «Circuit Hamiltonien modulo k» est Mod_{k}P-complet (puisque #SAT se réduit de manière parsimonieuse à «Circuit Hamiltonien», on en déduit que Mod_{k}SAT se réduit à «Circuit Hamiltonien modulo k»). Or, de même que pour le permanent, le nombre de circuits hamiltoniens d’un graphe s’obtient comme coefficient d’une certaine suite de polynômes (K_{n}) ∈ VΣ^{0}P à partir de sa matrice d’adjacence (x_{i,j}) (cf [15, lemme 14]) :

HC_{n}(x_{1,1} …, x_{n,n}) = ∑_{σ} ∏_{i=1}^{n} x_{i,σ(i)} = coef_{m}(K_{n}),

où la somme est prise sur tous les cycles σ de longueur n de {1, …, n}, et où K_{n} est de degré formel complet polynomial.

La définition de K_{n} est constructive, et on peut créer en temps polynomial un circuit calculant K_{n}. Ainsi, savoir si le nombre de circuits hamiltoniens d’un graphe est nul modulo k revient à savoir si le coefficent d’un monôme d’un polynôme calculé par un circuit constructible en temps polynomial est nul modulo k. Donc CMN_{k} est Mod_{k}P-dur.

2.3.2.2 Remarque Le théorème de Toda montre que PH ⊆ BPP^{⊕P}. [20] le généralise à

PH ⊆ BPP^{Mod_{k}P}

pour tout k, ce qui implique que CMN_{k} n’est pas dans la hiérarchie polynomiale sauf si elle s’effondre.

2.4 Le cas général

2.4.1 DEG est P-dur

Nous montrons que DEG est plus difficile que le Problème de la Valeur d’un Circuit (PVC). PVC est le langage consistant des couples (B, b) où B est un circuit booléen, sans variable en entrée, et b est la valeur de la sortie. PVC est un problème P-complet pour les réductions en espace logarithmique. Dans un circuit algébrique C, on va coder la sortie du circuit B.

Soit C_{0} le circuit algébrique (sans variable) qui simule B par des polynômes. Le circuit C est obtenu comme suit : on ajoute une entrée x à C_{0} (x est une variable), puis on multiplie x par la sortie de C_{0} (qui vaut b ∈ {0, 1}). C calcule le polynôme bx, dont le degré est 1 si b = 1, et ≤ 0 sinon. Ainsi, DEG sur l’entrée (C, 0) résoud PVC : DEG est P-dur pour la réduction en espace logarithmique.

2.4.2 Relation entre CMN et DEG

Bien entendu, les deux problèmes que nous avons étudiés jusqu’à présent sont liés, puisqu’ils concernent tous deux la nullité de certains coefficients : celui d’un monôme précis pour CMN, et ceux de chaque monôme d’une composante homogène pour DEG. Nous avons le lien suivant entre la complexité des deux problèmes :

DEG ∈ Co-NP^{CMN},

où Co-NP est l’ensemble des langages dont le complémentaire est dans NP.

En effet, deg(C) ≤ d est équivalent à (tout monôme de degré > d a un coefficient nul), ce qui se teste dans Co-NP avec appels à l’oracle CMN.

Ainsi, en caractéristique k > 0 (et sans restriction sur le degré formel complet du circuit), on en déduit que

DEG ∈ Co-NP^{Mod_{k}P}.

2.5 Récapitulatif

Afin de résumer les résultats de ce chapitre, nous les avons regroupés dans le tableau suivant (où on suppose que la hiérarchie polynomiale est stricte).

Caractéristique nulle  Caractéristique k > 0
Borne inférieure Borne supérieure Borne inférieure Borne supérieure
CMN_{b}  Hors de PH  P^{#P[1]}  Mod_{k}P
CMN  Hors de PH  PSPACE
DEG_{b}  Linéaire  Co-RP  Linéaire  Co-RP
DEG  P  PSPACE  P  Co-NP^{Mod_{k}P}

Conclusion

Dans ce rapport, nous avons abordé deux aspects du calcul de polynômes f ∈ K[x_{1}, …, x_{n}] par des circuits algébriques.

– Le premier chapitre a étudié une hiérarchie de classes de complexité du point de vue de la complexité algébrique, dans l’esprit de la hiérarchie polynomiale. Nous calculons des suites de polynômes définis par de grosses sommes ou de gros produits : une séparation de ces classes montrerait que ces sommes ou ces produits augmentent véritablement la puissance de calcul, et un effondrement aurait de nombreuses conséquences inattendues. Enfin, nous nous servons des gros produits pour créer un circuit de séparation d’hyperplans, ce qui nous donne un résultat de transfert sur les classes algébriques P et NP.

– Dans le second chapitre, nous avons étudié la manipulation par machine de Turing booléenne de polynômes donnés par des circuits. Nous envisageons deux problèmes, le calcul du degré d’un polynôme et le calcul du coefficient d’un monôme. Nous avons montré que dans un cas restreint, le degré se calcule efficacement par un algorithme probabiliste, mais que le coefficient du monôme est difficile. Des résultats pertinents dans le cas général (notamment pour le calcul du degré) semblent plus durs à atteindre.

Il serait intéressant d’étudier plus en détail la hiérarchie des (VΣ^{i}P) et (VΠ^{i}P) : séparer des classes ou montrer que des classes coïncident auraient des conséquences très importantes.

Par ailleurs, nous utilisons les gros produits pour séparer des hyperplans. Il semble naturel de vouloir séparer des hypersurfaces, puisque nos circuits sont capables de calculer des polynômes. Un résultat sur la séparation d’hypersurfaces permettrait peut-être d’énoncer des résultats de transfert sur NP_{(K,+,−,×,=)} et ℙ_{(K,+,−,×,=)}, c’est-à-dire d’utiliser la multiplication même dans NP, ce qui n’est pas le cas du résultat du chapitre 1.

Concernant la complexité des problèmes CMN et DEG, du travail reste à accomplir afin d’améliorer le tableau récapitulatif du chapitre 2. Par exemple, on pourrait essayer d’améliorer la borne supérieure PSPACE de CMN en caractéristique nulle. Ou encore de limiter l’écart entre la borne inférieure (P) et la borne supérieure (PSPACE ou Co-NP^{Mod_{k}P} selon la caractéristique) de DEG en version non bornée.

Notons enfin que sans la thèse de Guillaume Malod ([15]) et la perspicacité de Pascal Koiran, beaucoup de résultats n’auraient certainement pas eu leur place dans ce rapport. Je les remercie vivement, ainsi que les autres membres de l’équipe.

Bibliographie

[1] Richard Beigel and John Gill. Counting classes : Thresholds, parity, mods, and fewness. Theoretical Computer Science, 103(1) :3–23, 1992.

[2] Elwyn R. Berlekamp. Factoring polynomials over finite fields. Bell System Tech. Journal, 46 :1853–1859, 1967.

[3] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. Algebraic settings for the problem “P ≠ NP ?”. The Mathematics of Numerical Analysis, 42 :125–144, 1996.

[4] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. Complexity and Real Computation. Springer, 1998.

[5] Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over the real numbers : NP-completeness, recursive functions and universal machines. Bulletin of the Amer. Math. Soc., 21 :1–46, 1989.

[6] Peter Bürgisser. Completeness and Reduction in Algebraic Complexity Theory, volume 7 of Algorithms and Computation in Mathematics. Springer, 2000.

[7] James H. Davenport, Yvon Siret, and Évelyne Tournier. Computer Algebra. Academic Press, second edition, 1993.

[8] Lane A. Hemaspaandra and Mitsunori Ogihara. The Complexity Theory Companion. EATCS. Springer, 2002.

[9] Valentine Kabanets and Russel Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Electronic Colloquium on Computational Complexity, 55, 2002.

[10] Erich Kaltofen. Greatest common divisors of polynomials given by straight-line programs. Journal of the ACM, 35(1) :231–264, January 1988.

[11] Neal Koblitz. A Course in Number Theory and Cryptography, volume 114 of Graduate Texts in Mathematics. Springer-Verlag, 1987.

[12] Pascal Koiran. Computing over the reals with addition and order. Theoretical Computer Science, 133(1) :35–48, 1994.

[13] Pascal Koiran. Valiant’s model and the cost of computing integers. Technical report, LIP, January 2004.

[14] Édouard Lucas. Théorie des fonctions numériques simplement périodiques. American Journal of Mathematics pure and applied, 1 :184–240 and 289–321, 1878.

[15] Guillaume Malod. Polynômes et coefficients. PhD thesis, Université Claude Bernard Lyon 1, July 2003.

[16] Chistos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

[17] Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4) :701–717, October 1980.

[18] Victor Shoup. New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54 :435–447, 1990.

[19] Seinosuke Toda. On the computational power of PP and ⊕P. In Proc. 30th IEEE Symposium on the Foundations of Computer Science, pages 514–519, 1989.

[20] Seinosuke Toda and Mitsunori Ogiwara. Counting classes are at least as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 21 :316–328, 1992.

[21] Leslie G. Valiant. Completeness classes in algebra. In Proc. 11th ACM Symposium on Theory of Computing, pages 249–261, 1979.

[22] Leslie G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2) :189–201, 1979.

[23] Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8 :410–421, 1979.

Annexe A

Autour de l’hypothèse FPSPACE ⊆ GapP/poly

Dans le premier chapitre, nous avons utilisé l’hypothèse FPSPACE ⊆ GapP/poly. Pour essayer de donner une intuition un peu meilleure de cette hypothèse à partir de classes de langages plutôt que de classes de fonctions, nous étudions dans cette partie ce qu’elle implique, et ce qui l’implique. Si A est un langage sur l’alphabet Σ, et f : N → N une fonction, pour x ∈ Σ^{∗} on définit #A_{f}(x) par le cardinal de l’ensemble {y ∈ Σ^{f(|x|)} : (x, y) ∈ A}. Nous prendrons dans ce qui suit Σ = {0, 1}.

A.1 Une conséquence de FPSPACE ⊆ GapP/poly

Nous allons montrer le résultat suivant :

FPSPACE ⊆ GapP/poly ⇒ PSPACE ⊆ ⊕P/poly.

Soit L un langage de PSPACE. On définit une fonction f : {0, 1}^{∗} → {0, 1} par f(x) = 1 si et seulement si x ∈ L. Cette fonction est dans FPSPACE, puisqu’il suffit de tester l’appartenance à L. Ainsi, par hypothèse, f est dans GapP/poly. Par définition, il existe donc une fonction de conseil polynomiale u, deux langages A et B de P, et deux polynômes p et q, tels que

f(x) = #A_{p}(x, u(|x|)) − #B_{q}(x, u(|x|)).

Puisque notre fonction f prend ses valeurs dans {0, 1}, on en déduit que #A_{p}(x, u(|x|)) + #B_{q}(x, u(|x|)) est impair si et seulement si f(x) = 1, si et seulement si x ∈ L. Or le langage C définit par l’ensemble des mots (y, a, u, v), où a est de taille 1, u de taille p(|y|), et v de taille q(|y|), tels que

– si a = 0 alors v = 0 … 0 et (y, u) ∈ A;

– si a = 1 alors u = 0 … 0 et (y, v) ∈ B, vérifie #C_{p+q+1}(y) = #A_{p}(y) + #B_{q}(y), et est dans P. Ainsi,

L = {x : #C_{p+q+1}(x, u(|x|)) impair},

donc L ∈ ⊕P/poly.

Bien entendu, la version uniforme FPSPACE ⊆ GapP ⇒ PSPACE ⊆ ⊕P est vraie, et se montre de la même manière.

A.1.1 Remarque L’inclusion suivante est vraie (cf [8, cor. 4.10]) :

PH ⊆ ⊕P/poly.

A.2 Une conséquence de PSPACE ⊆ UP/poly

La réciproque du résultat précédent n’est pas claire, mais nous allons montrer le résultat suivant :

PSPACE ⊆ UP/poly ⇒ FPSPACE ⊆ GapP/poly.

En fait, pour simplifier la preuve, nous allons montrer la version uniforme du résultat, c’est-à-dire

PSPACE ⊆ UP ⇒ FPSPACE ⊆ GapP.

La preuve du cas non-uniforme est essentiellement la même.

Soit f une fonction de FPSPACE. Supposons f positive. Alors il existe un polynôme p tel que

f(x) = ∑_{i=0}^{p(|x|)} f_{i}(x)2^{i},

où les fonctions f_{i}, à valeurs dans {0, 1}, sont telles que A := {(x, i) : f_{i}(x) = 1} est dans PSPACE (pour simplifier, on supposera sans perte de généralité que i est codé en unaire : ainsi, la taille de i est p(|x|)). Par hypothèse, on a donc A ∈ UP. Ainsi, il existe un langage B de P, et un polynôme q, tels que

– si (x, i) ∈ A alors il existe un unique y, de taille q(|x|), tel que (x, i, y) ∈ B;

– si (x, i) ∉ A alors il n’existe aucun y de taille q(|x|) tel que (x, i, y) ∈ B.

On définit le langage C de P comme l’ensemble des mots (x, i, y, v), où y est de taille q(|x|), v est de taille p(|x|) et code en binaire un entier ≤ 2^{i} −1 (i.e. toutes ses p(|x|)−i+1 premières lettres sont 0), et tel que (x, i, y) ∈ B. Puisque A est dans UP, le cardinal de {(y, v) : (x, i, y, v) ∈ C} est f_{i}(x)2^{i}, pour tout i. Ainsi, #C_{2p+q}(x) = ∑_{i=0}^{p(|x|)} f_{i}(x)2^{i} = f(x). Ainsi, f est dans #P.

Si f prend aussi des valeurs négatives, en décomposant f selon ses parties positive et négative, on voit que f est alors la différence de deux fonctions de #P, c’est-à-dire une fonction de GapP.

A.3 Résumé

Pour résumer, nous avons montré les implications suivantes :

PSPACE ⊆ UP/poly ⇒ FPSPACE ⊆ GapP/poly ⇒ PSPACE ⊆ ⊕P/poly.