Systems of equations over free groups: structures and complexity

In the first part of the thesis, we give a description of the fully residually F quotients of F* <x,y>. The techniques we use rely extensively on the structure results of fully residually free groups developed by O. Kharlampovich, A. Miasnikov, and by Z. Sela. We also use the now classical theory of H. Bass and J.-P. Serre of the actions of groups on trees. As an application we completely recover the descriptions of the solutions sets of systems of equations in two variables given by Hmelevskii} and Ozhigov, the most precise to date, using completely algebraic methods. We also construct some examples to illustrate the richness of the theory. In the second part of the thesis, we prove some results on algorithmic complexity. First we show that the the problem of deciding the solvability of an arbitrary quadratic equation over a free group is NP-complete. We also give an algorithm for Stallings' Folding Process; a fundamental technique in geometric group theory; which, for a fixed free group, runs in worst case time O(n\log^*(n)).Dans la première partie de cette thèse, nous décrivons les quotients de F*<x,y> qui sont des F-groupes limites. Les techniques que nous utilisons proviennent des résultats sur la structure des groupes limites développées par O. Kharlampovich, A. Miasnikov et indépendamment par Z. Sela. Nous utilisons également la théorie maintenant classique de H. Bass et de J.-P. Serre sur les actions des groupes sur les arbres. Comme application nous redérivons les descriptions des solutions des systèmes d'équations à deux variables données par Hmelevskii et Ozhigov, qui jusqu'à présent demeurent les plus précis, mais cette fois-ci en utilisant des méthodes complètement algébriques. Nous construisons également des exemples qui illustrent la richesse de la théorie.Dans la deuxième partie de cette thèse, nous prouvons des résultats de complexité algorithmique. Tout d'abord nous démontrons que le problème de décider si une équation quadratique arbitraire sur un groupe libre a une solution est NP-complet. Nous donnons finalement un algorithme pour le processus du Stallings' Folding qui, donné un groupe libre fixe, opère en temps au plus O(n\log^*(n))