Abstract FR:

Cette these contribue au domaine de la theorie de la complexite. Nous avons etudie des classes de comptage definies dans le modele de machine turing et dans le modele de familles de circuits. Nous avons regroupe differents resultats concernant ces classes selon deux themes principaux : comptage positif et comptage relatif. Nous avons etabli une liste de proprietes communes de ces classes, par exemple la cloture par addition faible, par multiplication faible et par formation de coefficients binomiaux restreints. Nous avons mis l'accent sur les classes de comptage relatif et presente deux approches differentes pour definir ces classes et nous obtenons les classes gap et les classes diff. En particulier nous avons etudie les classes diffac#0 et gapac#0 des fonctions calculables par une famille de circuits arithmetiques de profondeur constante, de taille polynomiale et de degre entrant non borne avec un nombre non borne de portes de soustraction (respectivement avec une seule porte de soustraction a la sortie). Nous avons prouve que ces deux classes sont egales. Ce resultat a aussi permis de montrer que le calcul de la partie entiere de la fonction (x#1 + + x#n)/2 ne peut etre calcule par une famille de circuits arithmetiques de profondeur constante, de taille quasi-polynomiale et de degre entrant non borne qui ne contient aucune porte de soustraction.