Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Complet (complexité)
Résumé
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.
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.
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.
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, 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 telle que la classe BPPM (c'est la classe BPP avec oracle M) ne possède pas de problème complet.
Complexity Zoo de l'université de Waterloo.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées (42)
Concepts associés (11)
Problème NP-complet
En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l
Hiérarchie polynomiale
En théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP. La classe PH est l'union de toutes les classes de la hiérarchie polynomiale. Il existe plusieurs définitions équivalentes des classes de la hiérarchie polynomiale. On peut définir la hiérarchie à l'aide des quantificateurs universel () et existentiel ().
Réduction en espace logarithmique
En théorie de la complexité, une réduction en espace logarithmique est une réduction calculable par une machine de Turing disposant d'un espace de travail logarithmique. La machine de Turing utilisée pour une réduction en espace logarithmique est constituée de trois rubans au lieu d'un : un ruban d'entrée (en lecture seule), un ruban de travail (de taille logarithmique en la taille du ruban d'entrée), et un ruban de sortie (en écriture seule et tel que la tête d'écriture ne peut écrire deux fois sur une même case).