Théorie de la complexité des algorithmes - Définition

Problèmes C-complets ou C-difficiles

Définition

Soit C une classe de complexité (comme P, NP, PSPACE, etc.). On dit qu'un problème est C-difficile si ce problème est au moins aussi difficile que tous les problèmes dans C. Un problème C-difficile qui appartient à C est dit C-complet.

Formellement, on définit une notion de réduction : soient Π et Π' deux problèmes ; une réduction de Π' à Π est un algorithme (ou une machine) d'une complexité qu'on sait être inférieure à celle de la classe C transformant toute instance de Π' en une instance de Π. Ainsi, si l'on a un algorithme pour résoudre Π, on sait aussi résoudre Π'. On peut donc dire que Π est au moins aussi difficile à résoudre que Π', à la complexité de la réduction près.

Π est alors C-difficile si pour tout problème Π' de C, Π' se réduit à Π.

La relation de réduction étant réflexive et transitive, elle définit un préordre sur les problèmes. Ainsi, on la note usuellement avec le symbole ≤ : on a Π'≤Π si Π' se réduit à Π. Les problèmes C-difficiles sont les majorants de C et les problèmes C-complets sont les plus grands éléments de C.

Exemples

Les problèmes NP-complets sont un cas particulier important de ce concept. De manière standard, ils sont définis en autorisant uniquement des réductions dans P, c'est-à-dire que l'algorithme qui calcule le passage d'une instance de Π' à une instance de Π est polynomial (voir Réduction polynomiale). Le théorème de Cook-Levin, dû à Stephen Cook et à Leonid Levin, énonce qu'il existe un problème NP-complet. Plus précisément, Cook a montré que le problème SAT est NP-complet. On a par la suite établi la NP-complétude de nombreux autres problèmes.

On qualifie de NP-complets les problèmes décisionnels, c'est-à-dire ceux dont la réponse est de type binaire (oui/non, vrai/faux, 1/0, …). On qualifie de NP-difficiles les problèmes d'optimisation, c'est-à-dire que la réponse est de type numérique. À un problème d'optimisation NP-difficile est associé un problème de décision NP-complet, mais dire qu'un problème NP-difficile est aussi NP-complet est un abus de langage.

Quand on parle de problèmes P-complets ou P-difficiles on s'autorise uniquement des réductions dans LOGSPACE.

Réduction de problèmes

Pour montrer qu'un problème Π est C-difficile pour une classe C donnée, il y a deux façons de procéder : ou bien montrer que tout problème de C se réduit à Π, ou bien montrer qu’un problème C-complet se réduit à Π. Par exemple, démontrons avec la seconde méthode que le problème de la recherche de circuit hamiltonien dans un graphe orienté est NP-complet.

• Le problème est dans NP, autrement dit, il peut être résolu par un algorithme polynomial sur une machine non déterministe. Il suffit par exemple d'engendrer de façon non déterministe un circuit, puis de tester s'il est hamiltonien.
• On sait que le problème de la recherche d'un cycle hamiltonien dans un graphe non orienté est NP-difficile. Or un graphe non orienté peut se transformer en un graphe orienté en créant deux arcs opposés pour chaque arête. Il est donc possible de ramener le problème connu, NP-complet, à savoir chercher un cycle hamiltonien dans un graphe non orienté, au problème que nous voulons classer, à savoir chercher un circuit hamiltonien dans un graphe orienté. Le problème de l'existence d'un circuit hamiltonien est donc NP-complet.

Le problème ouvert P=NP

On a clairement P ⊆ NP car un algorithme déterministe est un algorithme non déterministe particulier, ce qui, dit en mots plus simples, signifie que si une solution peut être calculée en temps polynomial, alors elle peut être vérifiée en temps polynomial. En revanche, la réciproque : NP ⊆ P, qui est la véritable difficulté de l'égalité P = NP est un problème ouvert central d'informatique théorique. Il a été posé en 1970 indépendamment par Stephen Cook et Leonid Levin ; en 2000, l'institut Clay a mis ce problème dans sa liste des sept problèmes du prix du millénaire, proposant une récompense de plus de 1 000 000 $ à qui parviendra à décider si P et NP sont différents ou égaux.

La plupart des spécialistes conjecturent que les problèmes NP-complets ne sont pas solubles en un temps polynomial (donc, que P ≠ NP). Cela ne signifie pas pour autant que toute tentative de résoudre un problème NP-complet est vaine (voir la section « Résolution » de l'article sur la NP-complétude). Il existe de nombreuses approches (qui se sont finalement révélées irrémédiablement erronées) attaquant le problème P ≠ NP ; le spécialiste de la théorie de la compléxité Gerhard Woeginger maintient une liste de ces erreurs [1]. La revendication récente (6 août 2010) de Vinay Deolalikar, travaillant aux HP Labs, d'une démonstration de P ≠ NP a été la première à faire l'objet d'une attention relativement importante de nombreux mathématiciens et informaticiens de renoms, que ce soit sous la forme d'échanges dans des blogs ([2], [3], [4]), de journaux en ligne ou sous la forme plus construite d'un projet d'étude collaborative en ligne (du type projet "polymath" tel que promu par les médaillés Fields Terence Tao et Tim Gowers). Cette étude collaborative donne la liste des points où l'approche de Vinay Deolalikar achoppe actuellement [5].

Problèmes apparentés

• On ne sait pas si L = NL.

• On sait que PSPACE = NPSPACE.

• Pour résumer, on a L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME ⊆ NEXPTIME.

On sait de plus que NL ⊊ PSPACE. Donc deux classes au moins entre NL et PSPACE ne sont pas égales. On sait également que P ≠ EXPTIME.