Abstract FR:

Le developpement de la theorie des modeles finis a favorise une nouvelle approche de la notion de complexite algorithmique. L'identification des problemes combinatoires a des ensembles de structures finies a en effet permis l'interpretation des classes de complexite en terme de langages logiques. Nous prouvons dans ce cadre l'inclusion de la classe nlin des problemes reconnaissables en temps lineaire sur ram non deterministes dans la logique du second ordre monadique existentiel avec addition. Ceci permet d'affirmer la caracterisation par cette logique de la plupart des problemes np-complets usuels. Puis nous montrons qu'en presence du successeur, les classes de structures nlin coincident avec les ensembles de modeles des formules du second ordre existentiel fonctionnel unaire comportant une unique variable du premier ordre quantifiee universellement, et dont la matrice est une simple conjonction d'egalites. Cette caracterisation purement conjonctive, a bien des egards optimale, se generalise au temps polynomial. Enfin nous etablissons l'identite des langages rudimentaires et des langages caracterises par une formule du second ordre monadique. Nous obtenons en corollaire un resultat de representation des spectres en termes d'ensembles d'entiers rudimentaires