Problèmes de décision et d'évaluation en complexité algébrique
Institution:
École normale supérieure (Lyon ; 1987-2009)Disciplines:
Directors:
Abstract EN:
In this thesis we are essentially interested in questions concerning algebraic complexity classes of decision problems and of evaluation problems. More precisely, we study on the one hand the model of Blum, Shub and Smale (BSS) for the recognition of languages over arbitrary structures thanks to algebraic circuits, and on the other hand the model of Valiant for the computation of polynomials thanks to arithmetic circuits. Our results show that in order to separate complexity classes, it is easier to work on evaluation problems, that is, in Valiant's model. This confirms our intuition that, the model being simpler (there are no test gates), lower bounds should be easier to obtain. In particular, we show two transfer results. The first concerns the algebraic versions of P and NP: over a field of characteristic zero, the separation of P and NP in BSS model thanks to problems in NP "without multiplication" implies the separation of P and NP in Valiant's model. The second concerns the question "P=PSPACE?": after defining analogues of PSPACE in both algebraic models, we show that separating P and PSPACE, over the reals or over the complex field, is easier in Valiant's model. More succinctly, we also study the manipulation by Turing machines of polynomials given by arithmetic circuits. Indeed, this way of encoding polynomials can be much shorter than the list of monomials. But the study of two examples (computing the coefficient of a monomial and computing the degree of a polynomial) shows that the manipulation of polynomials given by circuits is hard, even if their degree is polynomial and if we work over a field of positive characteristic.
Abstract FR:
Dans cette thèse, on s'intéresse essentiellement à des questions concernant les classes de complexité algébrique de problèmes de décision et de problèmes d'évaluation. Plus précisément, nous étudions d'une part, le modèle de Blum, Shub et Smale (BSS) pour reconnaître des langages sur une structure quelconque grâce à des circuits algébriques, et d'autre part, le modèle de Valiant pour calculer des polynômes grâce à des circuits arithmétiques. Nos résultats montrent qu'afin de séparer des classes de complexité, il est moins difficile de travailler sur les problèmes d'évaluation, c'est-à-dire dans le modèle de Valiant. Cela confirme notre intuition que, le modèle étant plus simple (il n'y a pas de portes de tests), les résultats doivent être plus simples à obtenir. En particulier, nous montrons deux résultats de transfert. Le premier concerne les versions algébriques de P et NP : sur un corps de caractéristique nulle, séparer P et NP dans le modèle BSS grâce à des problèmes NP "sans multiplication" implique de séparer P et NP dans le modèle de Valiant. Le second concerne la question "P=PSPACE ?" : après avoir défini un analogue de PSPACE dans les deux modèles algébriques, nous montrons que séparer P de PSPACE, sur les réels ou sur les complexes, est moins difficile dans le modèle de Valiant. Par ailleurs, et plus brièvement, nous étudions également la manipulation par machines de Turing de polynômes donnés par des circuits arithmétiques. En effet, encoder des polynômes de cette façon peut être bien plus court que la liste de tous les monômes. Mais l'étude de deux exemples (calculer le coefficient d'un monôme et calculer le degré d'un polynôme) montre qu'il semble difficile de manipuler des polynômes donnés de cette façon, même lorsqu'ils sont de degré polynomial et que l'on travaille sur un corps de caractéristique non nulle.