Télécharger le fichier original (Mémoire de fin d’études)

Modèles de calcul et complexité

L’étude de la complexité des polynômes peut se faire dans différents cadres, avec différents modèles de calcul. Nous utiliserons le cadre booléen dont les deux grands modèles de calcul sont la machine de Turing et les circuits booléens, et le cadre de la théorie de Valiant qui utilise des circuits arithmétiques et leurs variantes comme modèles. Un troisième modèle, le modèle de Blum, Shub et Smale [10, 11] est souvent utilisé pour parler de complexité de problèmes concernant les polynômes mais il n’en sera pas question dans cette thèse.

Le modèle booléen

On suppose le lecteur familier du modèle de la machine de Turing et des classes de complexité les plus classiques qui s’y rattachent. Pour plus de détails sur ce sujet, on consultera les chapitres 1 à 4 de l’ouvrage de Sanjeev Arora et Boaz Barak [5]. On commence par rappeler quelques notions tout à fait basiques, puis on se penche sur quelques définitions un peu plus exotiques qui sont utilisées dans la suite.
Un langage booléen une partie de f0, 1g?, c’est-à-dire un ensemble de mots finis sur l’alphabet f0, 1g. Pour une fonction f : N ! N, la classe DTIME( f (n)) représente l’ensemble des langages reconnus par une machine de Turing déterministe en temps O( f (n)). De même, NTIME( f (n)) est la classe des langages reconnus par une machine de Turing non déterministe en temps O( f (n)). Pour s : N ! N, DSPACE(s(n)) (resp. NSPACE(s(n))) est la classe des langages reconnus par une machine de Turing déterministe (resp. non déterministe) utilisant un espace O(s(n)).
Les classes les plus classiques sont, par ordre d’inclusion,
– L = DSPACE(log n),
– P = Sk DTIME(nk),
– NP = Sk NTIME(nk),
– PSPACE = Sk DSPACE(nk) et
– EXP = Sk DTIME(2nk ).
On dit qu’un langage L se réduit en temps polynomial à un langage L0 s’il existe une fonction f , calculable en temps polynomial, telle que x 2 L si et seulement si f (x) 2 L0. On dit qu’un langage L est NP-difficile (resp. PSPACE-difficile) si tout langage de NP (resp. de PSPACE) se réduit à L en temps polynomial. Un langage est NP-complet (resp. PSPACE-complet) s’il est NP-difficile (resp. PSPACE-difficile) et qu’il appartient à la classe NP (resp. PSPACE).
On peut considérer des machines de Turing probabilistes. Ces machines peuvent, à chaque étape de calcul, tirer une pièce à pile ou face et utiliser la réponse comme aide à la décision. On peut alors parler de réduction probabiliste : un langage L se réduit en temps polynomial probabiliste à un langage L0 s’il existe une machine de Turing probabiliste fonctionnant en temps polynomial telle que la probabilité que M(x) 2 L0 si x 2 L est supérieure à 2/3, ainsi que la probabilité que M(x) 2/ L0 si x 2/ L0. Cette notion de réduction probabiliste permet de donner l’une des définitions de la classe AM 3 : c’est la classe des langages L qui se réduisent en temps polynomial probabiliste à un problème NP-complet. Puisque toute machine déterministe peut être vue comme une machine probabiliste qui ignore les résultats de ses tirages aléatoires, tout problème de NP se réduit de manière probabiliste à un problème NP-complet. En d’autres termes, NP AM.
On peut définir la notion de circuit booléen par analogie avec celle de circuit arithmétique. Un circuit booléen est un graphe orienté acyclique dont les sommets de degré entrant nul sont appelés entrées et sont étiquetés par des variables, et les autres sommets sont appelés des portes et étiquetés soit par ^, soit par _, soit par :. Une porte ^ est de degré entrant 2 et calcule le « et » de ses deux arguments. Une porte _ est également de degré entrant 2, et calcule le « ou » (inclusif) de ses arguments. Enfin une porte : est de degré entrant 1 et calcule la négation de son argument. Un circuit à n entrées accepte un mot w = w1 wn si son évaluation sur le mot w est 1. Un langage L est décidé par une suite de circuits (Cn) si pour tout n, l’ensemble des mots acceptés par Cn est exactement L \ f0, 1gn.
On peut définir des classes de complexité à partir de la notion de circuit. Par exemple pour tout k, la classe NCk est l’ensemble des langages décidés par une suite de circuits de taille polynomiale et de profondeur O(logk n).On définit également NC = Sk NCk.

Le modèle de Valiant

Cette partie est un survol rapide des bases de la théorie de Valiant [122]. Une référence pour ce chapitre est l’ouvrage de Peter Bürgisser [17], ainsi que la thèse de Guillaume Malod pour les variantes des classes de base [96].
On définit une notion de complexité pour un polynôme basée sur les circuits arithmétiques définis précédemment.
Définition 1.11
Soit f 2 K[X1, . . . , Xn]. Alors la complexité arithmétique de f est la taille L( f ) du plus petit circuit arithmétique représentant f .
De même, Lmd( f ) est la taille du plus petit circuit multiplicativement disjoint représentant f , Lws( f ) est la taille du plus petit circuit faiblement asymétrique représentant f et Le( f ) est la taille de la plus petite formule représentant f .
On ne définit pas de notion de complexité associée aux circuits asymé-triques et aux programmes à branchements puisqu’on verra dans le chapitre 3 que ces modèles sont équivalents aux circuits faiblement asymétriques.
On définit ensuite les classes de complexité du modèle de Valiant. Dans ce modèle de calcul, les langages sont des familles de polynômes indexées habituellement par les entiers naturels. On notera ( fn)n2N une telle famille, ou simplement ( fn), où fn 2 K[X1, . . . , Xv( n)] pour tout n. Une famille de polynômes est représentée par une famille de circuits (Cn)n2 N si pour tout n, le circuit Cn représente le polynôme fn.
Les deux premières classes définies sont les classes VP et VNP définies par Leslie G. Valiant [122]. La classe VP est le pendant algébrique de la classe booléenne P. Quant à VNP, on peut la voir comme la version algébrique de NP ou de la classe de comptage #P. On note que ces classes dépendent en réalité du corps K dans lequel vivent les coefficients des polynômes considérés. Il y a donc autant de classes VP et VNP que de corps.
Une suite (un) est dite polynomialement bornée s’il existe une fonction polynomiale p telle que un p(n) pour tout n.
Définition 1.12
Soit K un corps.
La classe VP est l’ensemble des familles de polynômes ( fn) telles (deg( fn)) et (L( fn)) sont polynomialement bornées.
La classe VNP est l’ensemble des familles de polynômes ( fn) telles qu’il existe une famille (gn) 2 VP telle que pour tout n
fn(X) = å gn(X, e)
e2f0,1gw(n)
où X = (X1, . . . , Xv(n)) et e = (e1, . . . , ew(n)).
On peut définir VP de la manière équivalente suivante : une famille ( fn) appartient à VP si (Lmd( fn)) est polynomialement bornée. De la même manière, on définit trois variantes de VP et une variante de VNP.
Définition 1.13
Soit ( fn), fn 2 K[X1, . . . , Xv(n)]. Alors
– ( fn) 2 VPnb si (L( fn)) est polynomialement bornée ;
– ( fn) 2 VPws si (Lws( fn)) est polynomialement bornée ;
– ( fn) 2 VPe si (Le( fn)) est polynomialement bornée.
La classe VNPnb est définie par analogie à VNP en remplaçant VP par VPnb.
On pourrait définir de même VNPws et VNPe, mais Valiant a prouvé que VNPe = VNP, et donc VNPws est aussi égal à VNP [122]. On a les inclusions
VPe VPws VP ( VPnb.
L’inclusion stricte vient du fait que VPnb contient des familles de polynômes dont le degré n’est pas polynomialement borné comme par exemple la famille (X2n ), contrairement aux autres. On a également VP VNP ( VNPnb.
On définit ensuite la notion de circuit sans constante, ainsi qu’une notion de complexité associée.
Définition 1.14
Un circuit arithmétique sans constante est un circuit dont les entrées sont étiquetées soit par une variable, soit par l’entier relatif 1. Un circuit sans constante représente un polynôme f 2 Z[X1, . . . , Xn].
Pour f 2 Z[X1, . . . , Xn], la t-complexité de f , notée t( f ), est la taille du plus petit circuit sans constante représentant f . Les mesures de complexité tmd( f ), tws( f ) et te( f ) sont définies de manière analogue.
On remarque que pour tout f 2 Z[X1, . . . , Xn], L( f ) t( f ). Guillaume Malod a défini des versions sans constante des classes de Valiant [96].
Définition 1.15
La classe VP0 est l’ensemble des familles ( fn) de polynômes à coefficients entiers telles que (deg( fn)) et (t( fn)) sont polynomialement bornées. De manière équivalente, (tmd( fn)) est polynomialement bornée.
Par analogie, on peut définir les classes VNP0, VP0e, VP0ws, VP0nb et VNP0nb.
Une notion importante en complexité est celle de réduction. Dans le cadre de la complexité de Valiant, la notion la plus communément utilisée est celle de p-projection.
Définition 1.16
Un polynôme g 2 K[Y1, . . . , Ym] est une projection d’un polynôme f 2 K[X1, . . . , Xn] s’il existe une fonction de projection p : fX1, . . . , Xng ! K [ fY1, . . . , Ymg telle que g(Y1, . . . , Ym) = f (p(X1), . . . , p(Xn)).
Une famille (gn) de polynômes est une p-projection d’une famille ( fn) s’il existe une fonction polynomiale p telle que pour tout n, gn soit une projection de fp(n).
Soit VC une classe de complexité de Valiant. Une famille ( fn) est dite VC-complète si ( fn) 2 VC et si toute famille (gn) 2 VC est une p-projection de ( fn).
Pour les classes sans constante, on impose de plus que la projection soit bornée, c’est-à-dire que chaque constante utilisée doit pouvoir être calculée à partir de la constante 1 par un circuit multiplicativement disjoint de taille polynomiale.
On donne maintenant les deux exemples de familles de polynômes que l’on va principalement rencontrer par la suite. Soit X = (Xij)1 i,j n la matrice dont les coefficients sont n2 indéterminées. La famille (Detn) est définie par Detn = det(X ) pour tout n. Soit M = (mij)1 i,j n une matrice. Alors son permanent est
per(M) = å Õmis(i).
s2Sn j=1
Le permanent est donc un objet très proche du déterminant, mais il est en réalité bien plus difficile à calculer. La famille (Pern) est définie par Pern = per(X ) pour tout n.
La famille (Detn) est VPws-complète [120, 96, 97] et la famille (Pern) est VNP-complète [122]. Bien entendu, on ne sait pas séparer les classes VP et VNP, et la question « VP = VNP ? » est vue comme l’analogue algébrique de « P=NP ? ». On note qu’on ne sait pas non plus séparer VPe ou VPws de VNP.

Table des matières

Introduction 
1 Prolégomènes 
1.1 Polynômes, déterminants et graphes
1.1.1 Polynômes
1.1.2 Déterminants
1.1.3 Graphes
1.2 Représenter les polynômes
1.2.1 Représentations dense, creuse et lacunaire
1.2.2 Les circuits arithmétiques
1.2.3 Les programmes à branchements
1.3 Modèles de calcul et complexité
1.3.1 Le modèle booléen
1.3.2 Le modèle de Valiant
I Résolution des systèmes polynomiaux 
2 Complexité du résultant multivarié 
2.1 Complexité du résultant en caractéristique nulle
2.1.1 Borne supérieure
2.1.2 Borne inférieure
2.2 NP-difficulté en caractéristique quelconque
2.2.1 Une réduction probabiliste
2.2.2 Deux réductions déterministes
2.3 Matrices de Macaulay
2.3.1 Représentation des matrices de Macaulay
2.3.2 Déterminant d’une matrice représentée par un circuit
II Représentations déterminantielles de polynômes 
3 Complexité déterminantielle 
3.1 Taille réduite
3.2 Circuits et programmes à branchements
3.2.1 Formules et programmes à branchements
3.2.2 Circuits asymétriques
3.3 Complexité du déterminant
3.3.1 Expressivité du déterminant
3.3.2 Un programme à branchements pour le déterminant
3.4 Complexité déterminantielle du permanent
4 Représentations symétriques 
4.1 Représentation symétrique des programmes à branchements
4.2 Comparaisons avec des résultats existants
5 Représentations symétriques en caractéristique deux 
5.1 Prérequis algébrique
5.1.1 Polynômes, déterminants et graphes en caractéristique 2
5.1.2 Anneaux quotient
5.2 Polynômes représentables
5.3 Obstructions aux représentations
5.3.1 Condition nécessaire
5.3.2 Exemple
5.3.3 Polynômes multilinéaires
5.3.4 Vers une caractérisation complète ?
5.4 Représentation et factorisation des polynômes multilinéaires
5.4.1 Résultats préliminaires
5.4.2 Test de factorisabilité
5.4.3 Algorithme de représentation
5.5 Représentations déterminantielles alternées
III Polynômes de type creux 
6 Autour de la t-conjecture réelle 
6.1 La t-conjecture réelle
6.1.1 Travaux existants
6.1.2 Notre approche
6.2 Racines réelles des sommes de produits de polynômes creux
6.2.1 Définitions
6.2.2 Une généralisation de la règle de Descartes
6.2.3 Affinement de l’analyse
6.3 Borne inférieure pour le permanent
6.4 Tests d’identité polynomiale
6.5 Conclusion
7 Factorisation des polynômes lacunaires à deux variables 
7.1 Valuation et théorème de lacune
7.1.1 Preuve du théorème 7.1
7.1.2 Des améliorations possibles ?
7.1.3 Un théorème de lacune
7.2 Algorithmes
7.3 Généralisations
7.3.1 Une borne générale sur la valuation
7.3.2 Généralisations des algorithmes
7.4 Caractéristique positive
Bibliographie 

Télécharger le rapport complet