20/05/2007

Problèmes C-Complets

La notion de problème C-Complet est très importante dans la théorie de la complexité. Nous allons donc tout d’abord voir ce qu’est la réduction d’un problème dans une classe C, et pourquoi cette notion est nécessaire, puis expliquer ce qu’est un problème difficile, et enfin finir par un exemple d’un problème NP-Complet. Les problèmes de cette classe(NP) étant de loin les plus étudiés, nous allons expliquer l’un des plus connus, le problème SAT.

La réduction :

Une réduction d’un problème P vers un problème P’ est une transformation de toute instance de P en instance de P’. Ainsi, il y a une relation de difficulté de résolution entre ces deux problèmes. Si P’ est facile, alors P le sera aussi, et inversement, si P est difficile, alors P’ le sera de même.

 

Néanmoins, il y a plusieurs types de réduction. Celle de base est la réduction de Cook. C’est la transformation par une machine de Turing polynomial ‘oracle’ (c'est-à-dire qui qui peut accéder a des informations qu’elle ne peut pas forcément calculer). Soit une réduction de Cook d’un problème P vers un problème P’, alors il existe une machine de Turing oracle qui peut résoudre P en se servant des informations obtenu par P’.

 

Vient ensuite la réduction de Karp, qui est en fait un cas particulier de celle de Cook. C’est une fonction de transformation calculable en temps polynomial. Le plus souvent, quand le terme « réduction » sans autre précision est utilisé, c’est pour faire référence à cette réduction. La réduction de Cook étant plus lourde, elle est plus rarement utilisée, car ses propriétés sont rarement intéressantes. Il y a d’autres réductions, mais ces deux la sont les plus utilisées.

 

Chaque classe complète considère implicitement un type de réduction. Les problèmes NP-Complet par exemple utilisent la réduction de Karp, c'est-à-dire que l’algorithme de transformation est polynomial, mais nous allons voir ça plus loin.

 

La réduction permet de définir ci-dessus le problème C-Hard.

 

Problèmes C-Hard :

Soit un problème P. Si pour tout problème P’ dans la classe C, il existe une réduction de P’ vers P, alors P est un problème C-hard.

 

Formellement, un problème est toujours C-hard suivant un certain type de réduction, ainsi, on dira : «Ce problème est C-Hard sous la réduction de Levin ».

 

Pour montrer qu'un problème P est C-hard pour une classe C donnée, il y a deux façons de procéder: montrer que tout problème de C se réduit à P, ou bien il suffit de montrer qu’un problème C-hard se réduit à P. C’est très souvent la seconde méthode qui est utilisé, car il suffit de se baser sur les problème C-hard connus et en trouver un réductible a P.

 

Problèmes C-Complet :

Une fois assimilée la réduction, et les problèmes C-Hard, la définition ne posent plus aucun problème :

- Le problème doit appartenir à C.

- Le problème doit être C-hard suivant une certaine réduction.

 

A savoir que la réduction n’est pas toujours la même suivant la classe, comme cité précédemment, pour la classe NP, par exemple, c’est la réduction de Karp qui est nécessaire.

 

Maintenant que cette notion est définit, un exemple de problème Complet va être expliquer.

 

 

Un problème NP-Complet, SAT :

Ce problème est l’un des plus connus dans le domaine de la complexité, et en particulier de la NP-Complétude. Le problème est le suivant :

 

Nous possédons une formule algébrique booléenne, et on veut déterminer sa satisfiabilité. Par exemple : (a and B) or (c and (not e))

 

Le but est de savoir si cette formule peut être vraie d’après les lois booléennes classique en attribuant des valeurs aux variables utilisés. L’exemple est évidemment très simple, mais dans la pratique, la résolution de ce problème est extrêmement lourde. Il est possible de prouver que ce problème est NP-Complet, mais ce n’est pas le but ici.

 

La plus évidente des méthodes pour résoudre ce problème est de parcourir la table de vérité du problème, mais la complexité est alors exponentielle par rapport au nombre de variables. Des méthodes de résolution plus efficaces que le ‘brute force’ ont été mises au point et ont permis de faire évoluer l’algorithmie et l’étude de la complexité.

 

Ce problème, réputé pour être l’un des premiers à avoir été étudié, a été suivi par bon nombre de problèmes tous aussi réputés, comme celui du voyageur de commerce, du sac a dos, ou encore la coloration de graphe, qui sont devenus des grands classiques.