Abstract FR:

Cette these est consacree a l'etude des liens entre le temps lineaire et les problemes np-complets. Nous etudions tout d'abord les reductions lineaires entre problemes np-complets et les classes d'equivalence qu'elles induisent. De nombreux problemes sont montres etre lineairement equivalents a la satisfaisabilite. Dans ce cadre une methode uniforme pour prouver la np-completude est developpee. Elle est centree sur un probleme cle: la 3-colorabilite. Deux autres classes d'equivalence sont mises en evidence, l'une contenant dominating set et l'autre max-2sat. Cette derniere met en jeu des problemes d'optimisation et permet de montrer que divers problemes tels max-sat, max-2sat, min-2sat et simple max-cut sont lineairement equivalents. Nous proposons finalement de nouveaux problemes nlinear-complets, c'est-a-dire complets pour le temps lineaire non deterministe. Nous obtenons ainsi une borne inferieure non triviale de complexite pour chacun d'entre eux. Ces problemes portent sur les graphes orientes et non orientes