∑
MathTCG
#028 / 100•Space, Chance & Computation•MathTCG #428 / 500•★★★Rare•∀Logique•Concept

NP-complétude

Période historique : 1971

La classe des problèmes les plus difficiles de NP : résoudre l'un en temps polynomial résoudrait tous les autres.

Contenu & Formulation mathématique

Définition rigoureuse
La classe des problèmes les plus difficiles de NP : résoudre l'un en temps polynomial résoudrait tous les autres.
L∈NPC  ⟺  (L∈NP  ∧  ∀L′∈NP, L′≤PL)L \in \mathbf{NPC} \iff (L \in \mathbf{NP} \;\land\; \forall L' \in \mathbf{NP}, \, L' \le_P L)

Genèse & Portée historique

Un problème de décision est NP-complet s'il est dans NP et si tout problème de NP s'y réduit en temps polynomial (NP-difficile). Stephen Cook (1971) et Leonid Levin (1973) ont prouvé que le problème de satisfiabilité booléenne (SAT) est NP-complet. Richard Karp a ensuite identifié 21 problèmes fondamentaux NP-complets en 1972.

La liste de Karp incluait le voyageur de commerce, la clique maximale, le coloriage de graphe et le sac à dos, établissant la NP-complétude comme la référence universelle de l'intraitabilité algorithmique.

« La clé de voûte de la complexité : faites plier un seul problème NP-complet, et tous s'inclinent. »

Filiations & Relations conceptuelles (2)

Repose sur le concept#401

Problème P contre NP

Les problèmes NP-complets sont le cœur de la question P contre NP.

Fondement conceptuel de#455

Problème du voyageur de commerce

Le problème du voyageur de commerce est l'archétype des problèmes NP-difficiles.

Objet de collection MathTCG

#428
★★★Rare
∀

NP-complétude

Logique•CONCEPT

La classe des problèmes les plus difficiles de NP : résoudre l'un en temps polynomial résoudrait tous les autres.

L∈NPC  ⟺  (L∈NP  ∧  ∀L′∈NP, L′≤PL)L \in \mathbf{NPC} \iff (L \in \mathbf{NP} \;\land\; \forall L' \in \mathbf{NP}, \, L' \le_P L)
1971

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Space, Chance & Computation.

Extension : Space, Chance & Computation (#028 / 100)
Numéro global MathTCG : MathTCG #428 / 500
Rareté officielle : Rare (★★★)
Domaine théorique : Logique
Identifiant pérenne : np-completude
Consulter mon classeurExplorer tout le recueil