Complet (complexité)

Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En informatique théorique, et notamment en théorie de la complexité, un problème complet pour une classe de complexité est un problème de décision qui fait partie des problèmes les plus difficiles à résoudre de cette classe. En ce sens, il est un représentant de la classe. C'est une notion centrale en complexité. Elle permet notamment d'établir des inclusions entre les classes en ne considérant qu'un seul problème.

Définition formelle

Un problème p est dit difficile pour une classe C pour un certain type de réduction s'il existe une réduction de ce type, depuis n'importe quel problème de la classe vers p. Il est complet pour la classe C, ou C-complet, s'il est difficile pour la classe C et appartient à C.

Exemples

Le problème de la satisfiabilité des formules logiques (restreint à trois littéraux), 3-SAT est l'un des problèmes complets classiques de la classe NP.

Propriétés

Pour prouver qu'une classe C est contenue dans une classe C’, il suffit de démontrer qu'un problème C-complet appartient à la classe C’.
En particulier, si un problème est complet pour deux classes de complexité C et C’, alors C=C’. Un exemple de ce principe est le théorème de Shamir, qui établit l'égalité IP = PSPACE, où IP est la classe des problèmes possédant une preuve interactive en temps polynomial.
En général, les classes de complexité récursivement énumérables possèdent des problèmes complets connus. Il en est ainsi par exemple pour NP, co-NP, PLS (en) ou PPA.
Pour certaines classes comme RP, ZPP ou BPP, on ne connaît pas de problème complet.
Pour d'autres classes encore, on sait qu'il n'y a pas de problème complet. Par exemple, Michael Sipser a prouvé qu'il existe un langage M tel que la classe BPP^M (c'est la classe BPP avec oracle M) ne possède pas de problème complet^[1].

Notes et références

↑ M. Sipser. « On relativization and the existence of complete sets », Proceedings of ICALP'82, Springer-Verlag, Lecture Notes in Computer Science volume 140, p. 523-531, 1982.

Liens externes

(en) Complexity Zoo de l'université de Waterloo.

Portail de l'informatique théorique

[1] M. Sipser. « On relativization and the existence of complete sets », Proceedings of ICALP'82, Springer-Verlag, Lecture Notes in Computer Science volume 140, p. 523-531, 1982.

[1]