Abstract FR:

Ce travail porte sur l'etude de la complexite du calcul parallele dans le modele des circuits booleens et ses liens avec la classification algebrique des monoides finis. Barrington a montre qu'un langage est reconnu par une suite de circuits nc#1 ssi il est reconnu par une suite de programmes de longueur polynomiale sur un monoide fini. Ceci nous permet d'utiliser la classification algebrique des monoides finis, en termes de varietes, afin d'etudier la structure interne de la classe nc#1. Nous donnons des caracterisations algebriques detaillees des sous-classes de nc#1, reliant plus precisement la nature des portes et la profondeur des circuits a la complexite des varietes de monoides. Contrairement a la reconnaissance par morphismes, deux varietes distinctes de monoides peuvent, avec des programmes de longueur polynomiale, reconnaitre la meme classe de langages. Ceci nous amene, a travers une etude des proprietes du probleme du mot, a definir une nouvelle division entre monoides finis et une nouvelle notion de variete de monoides finis, adaptee a la reconnaissance par programmes. A l'aide de cette notion, nous demontrons que pour toutes les classes de circuits (sauf une) contenues dans nc#1, si deux classes sont separables, alors elles sont separees par un langage rationnel. Les classes de complexite a l'interieur de nc#1 ont egalement des caracterisations en logique, tout comme les langages rationnels. La seule difference est l'utilisation de predicats numeriques non-uniformes dans le cas des circuits, un predicat numerique etant un predicat qui definit un sous-ensemble de n#k. Nous demontrons qu'il existe une unique classe maximale de predicats numeriques telle que les langages, definis par des formules n'utilisant que des predicats numeriques de cette classe, sont rationnels. Ce resultat, avec les caracterisations algebriques, permet d'enoncer une conjecture tres forte concernant