Problèmes NP-complets

Quelques définitions

On distingue trois classes de problèmes P, NP, NP-complet.

coût

P

Un problème appartient à la classe P s’il peut être décidé en temps polynomial.

NP

Un problème de décision est dans NP s’il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l’entrée. Cela implique que pour un problème A, il est possible de vérifier qu’un mot m est solution de A en temps polynomial.

NP-complet

Un problème NP-complet est un problème qui n’admet pas d’algorithmes capables de trouver une solution en un temps polynomial. Plus précisément, pour deux problèmes A et B de cette classe, il existe une transformation (ou réduction) f qui transforme le problème A en B.

BPP

La classe BPP est un objet de la théorie de la complexité, en informatique théorique. C’est une classe de problèmes de décision qui peut être définie avec des machines de Turing probabilistes. L’acronyme BPP vient de Bounded-error Probabilistic Polynomial time.

P=NP ?

C’est un problème encore irrésolu : Problème P = NP.

Idée pour démonstration qu’un problème est NP-complet

Une preuve complète est donnée dans le cours Logique, modèles, calculs (INF 423).

1

L’idée est toujours la même : il faut partir d’un problème NP-complet connu et le réduire de façon polynomial au problème P dont on cherche à démontrer qu’il est NP-complet. La réduction est une transformation d’un problème A en P de telle sorte qu’une solution problème A puisse être transformé en une solution du problème P et réciproquement.

2

Il faut un premier problème NP-complet pour lequel il faut démontrer la NP-complétude. C’est le théorème de Stephen Cook : le problème SAT est NP-complet. On peut montrer que les problème SAT et 3-SAT sont équivalents.

3

Beaucoup de problèmes se présentent sous la forme d’une optimisation. Or SAT est un problème de décision : existe-t-il un point de \acc{0,1}^N qui vérifie une clause logique : \vee_k  ( y_{1k} \wedge ... \wedge y_{n_k k} ) avec y_{ik} est soit x_i soit \neg x_i ? Pour passer de l’un à l’autre, on transforme le problème d’optimisation en un problème de décision : existe-t-il une solution dont l’évaluation est inférieure ou supérieur à un certain seuil ?