Ceci est une liste des problèmes NP-complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d'un problème de décision. Puisqu'on connaît plus de 3000 problèmes NP-complets, cette liste n'est pas exhaustive. La plupart des problèmes énumérés proviennent du livre fondamental de Garey et Johnson : Computers and Intractability: A Guide to the Theory of NP-CompletenessM.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman. 1983. .. Ils sont présentés ici suivant les mêmes ordre et organisation.
Géométrie algorithmique
d'un ensemble de points dans le planMinimum Weight Triangulation is NP-Hard, 22nd SCG (2006) Tester si un arbre peut être représenté comme un arbre couvrant minimum euclidien Reconnaissance d'un graphe de disques unitaires (c'est le graphe d'intersection du cercle unitaire dans le plan)H. Breu and D. G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998 Plusieurs problèmes de planification de mouvement au travers des obstacles polygonaux dans le plan sont NP-difficiles. Partition planaire en sous-assemblements connectés : étant donné un ensemble A de polygones dans le plan qui peuvent se toucher mais ne se chevauchent pas, décider s'il y a un sous-ensemble non-trivial S de A qui peut être séparé de A\S par un déplacement rigide et sans collision de S et tel que S et A\S sont connectés"Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165..
Théorie des graphes
Couverture et découpage en partitions
Couverture par sommets · Ensemble dominant · Nombre domatique · Coloration de graphe à k couleurs · Nombre achromatique · · Coupe-cycles de sommets (feedback vertex set) · Ensemble d'arcs à rétroaction · Ensembles de côtés à rétroaction partielle · · Partition en triangles · Partition en sous-graphes isomorphiques · Partition en sous-graphes hamiltoniens · Partition en forêts · Partition en cliques · Partition en pairages parfaits · Pairage stochastique de poids maximum en deux étapes · · Couverture par sous-graphes bipartis complets
Sous-graphes et super-graphes
Clique maximum . Stable maximum · Ensemble indépendant · Sous-graphe maximum induit ayant une propriété P · Sous-graphe connexe maximum induit ayant une propriété P · · Sous-graphe biparti équilibré complet · Sous-graphe biparti · Sous-graphe connexe maximum de degré borné · Sous-graphe planaire · · Transitive subgraph · Uniconnected subgraph · Minimum k-connected subgraph · Cubic subgraph · Minimum equivalent digraph · Hamiltonian completion · Interval graph completion · Path graph completion
Tri des sommets
Cycle hamiltonien · Cycle hamiltonien orienté · Chemin hamiltonien · Problème de la bande passante · Problème de la bande passante orientée · Arrangement linéaire optimal · Arrangement linéaire optimal orienté · Coupure minimale d'un arrangement linéaire · Arrangement d'un arbre enraciné · Directed elimination ordering · Elimination degree sequence
Morphismes
Problème de l'isomorphisme de sous-graphes · Plus grand sous-graphe commun · Maximum subgraph matching · Graph contractability · Digraph D-morphism
Divers
Chemin avec paires interdites · Multiple choice matching · Nombre de Grundy d'un graphe orienté · Kernel · K-closure · Intersection graph basis · Path distinguishers · · Nesetril-Rödl dimension · Threshold number · Diamètre orienté · Diamètre pondéré
Conception de réseau
Arbres couvrants
Degree constrained spanning tree · Maximum leaf spanning tree · Shortest total path length spanning tree · Bounded diameter spanning tree · Capacitated spanning tree · Geometric capacitated spanning tree · Optimum communication spanning tree · Isomorphic spanning tree · Kth best spanning tree · Bounded component spanning forest · Multiple choice branching · Arbre de Steiner · Geometric Steiner tree · Cable Trench Problem
Coupures et connexité Partition de graphe · Partition acyclique · Problème de la coupe maximum (Max-cut) · Minimum cut into bounded sets · Augmentation biconnexe · Augmentation fortement connexe · Network reliability · Network survivability · Coupure multivoie ·
Routage
· Problème du postier chinois · Voyageur de commerce euclidien · K arcs les plus vitaux · · Metric traveling salesman · circuit le plus long · Problème de la plus longue chaîne · Prize Collecting Traveling Salesman · Problème du facteur rural · Shortest path in general networks · Shortest weight-constrained path · Stacker-crane · Time constrained traveling salesman feasibility · Problème du voyageur de commerce · Problème de tournées de véhicules
Flux
Minimum edge-cost flow · Integral flow with multipliers · Path constrained network flow · Integral flow with homologous arcs · Integral flow with bundles · Undirected flow with lower bounds · Directed two-commodity integral flow · Undirected two-commodity integral flow · Disjoint connecting paths · Maximum length-bounded disjoint paths · Maximum fixed-length disjoint paths · Unsplittable multicommodity flow
Divers Problème d'affectation quadratique · Minimizing dummy activities in PERT networks · Triangulation contrainte · Intersection graph for segments on a grid · Edge embedding on a grid · Geometric connected dominating set · Minimum broadcast time · Min-max multicenter · Min-sum multicenter · Uncapacitated Facility Location · k-centre · k-médiane
Ensembles et partitions
Couverture, échantillonnage et partition
Appariement à 3 dimensions · Couverture exacte · Set packing · · Problème de couverture par ensembles · Minimum test set · Set basis · Hitting set · Intersection pattern · Comparative containment · 3-matroid intersection
Ensembles avec poids assignés
Partition · Somme de sous-ensembles · Produit de sous-ensembles · 3-partition · Numerical 3-dimensional matching · Numerical matching with target sums · Expected component sum · somme minimale de carrés · Kth largest subset · Kth largest m-tuple
Stockage d'information et accès
Stockage d'information
Bin packing · Dynamic storage allocation · Pruned trie space minimization · Expected retrieval cost · Rooted tree storage assignment · Multiple copy file allocation · Capacity assignment
Compression et représentation
Plus courte super-séquence commune . Plus longue sous-séquence commune dans le cas d'un nombre de séquences d'entrée arbitraire (c'est-à-dire non fixé a priori) même dans le cas d'un alphabet binaire. · Problème de correspondance de Post borné · Hitting string · Compression de matrice creuse · Consecutive ones submatrix · Consecutive ones matrix partition · Consecutive ones matrix augmentation · Consecutive block minimization · Consecutive sets · 2-dimensional consecutive sets · · Grouping by swapping · External macro data compression · Internal macro data compression · Regular expression substitution · Rectilinear picture compression · Optimal vector quantization codebook · Minimal grammar-based compression
Bases de données
Minimum cardinality key · Additional key · Prime attribute name · Boyce-Codd normal form violation · Conjunctive query foldability · · Tableau equivalence · Serializability of database histories · Safety of database transaction systems · Consistency of database frequency tables · Safety of file protection systems
Ordonnancement Ordonnancement dans les systèmes d'exploitation
Sur un processeur unique Sequencing with release times and deadlines · Sequencing to minimize Tardy tasks · Sequencing to minimize Tardy weight · Sequencing to minimize weighted completion time · Sequencing to minimize weighted tardiness · Sequencing with deadlines and set-up times · Sequencing to minimize maximum cumulative cost
Sur plusieurs processeurs
· Precedence constrained scheduling · Resource constrained scheduling · Scheduling with individual deadlines · Preemptive scheduling · Scheduling to minimize weighted completion time
Ordonnancement manufacturier
· Flow-shop scheduling · No-wait flow-shop scheduling · Two-processor flow-shop with bounded buffer · Séquençage de tâches
Divers Timetable design · Staff scheduling · Production planning · Evitemment des interblocages . Resource-constrained scheduling problem
Optimisation
Optimisation continue
Il y a moins de problèmes NP-ardus (pas NP-complets, car ce ne sont pas des problèmes de décision) en optimisation continue qu'en optimisation combinatoire, car en optimisation continue, les problèmes ne peuvent être résolus en un nombre fini d'opérations, si bien que la complexité de ces problèmes n'est pas définie. Deux exceptions à cette affirmation : l'optimisation linéaire qui est dans P et l'optimisation quadratique.
Optimisation quadratique : NP-ardu si la fonction-objectif n'est pas convexe ; dans P sinon.
Optimisation combinatoire
Optimisation linéaire en nombres entiers · · Cost-parametric linear programming · Feasible basis extension · Minimum weight solution to linear equations · Open hemisphere · K-relevancy · Traveling salesman polytope non-adjacency · Sac à dos · Sac à dos entier · Sac à dos à choix multiple · Sac à dos partiellement ordonné · Comparative vector inequalities ·
Algèbre et théorie des nombres
Problèmes de divisibilité
Congruence quadratique · Incongruence simultanée · Divisibilité simultanée de polynômes linéaires · Comparative divisibility · Exponential expression divisibility · Non-divisibility of a product polynomial · Non-trivial greatest common divisor
Résolubilité d'équations
Équations quadratiques diophantiennes · Algebraic equations over GF · Root of modulus 1 · Number of roots for a product polynomial · Periodic solution recurrence relation
Divers Permanent evaluation · Cosine product integration · Equilibrium point · Unification with commutative operators · Unification for finitely presented algebras · Integer expression membership
Jeux
Generalized hex · Generalized geography · Generalized Kayles · Sequential truth assignment · Variable partition truth assignment · Sift · Alternating hitting set · Alternating maximum weighted matching · Annihilation · Left-right Hackenbush for Redwood furniture · Square-tiling · Crossword puzzle construction · Generalized instant insanity · Démineur · Sudoku · Nurikabe · Picross · Hashiwokakero · · Slither Link · Kakuro · · Tetrisbeauté mathématique en chronologie Futura Sciences · Mastermind · Masyu · Lemmings
Logique
Logique propositionnelle Problème SAT · Problème 3SAT · Not-all-equal 3SAT · One-in-three 3SAT · Maximum 3-Satisfiability · Generalized satisfiability · Satisfiability of boolean expressions · Non-tautology · Minimum disjunctive normal form · Truth-functionally complete connectives
Divers First order theory of equality · Modal logic S5-Satisfiability · Modal logic provability · Predicate logic without negation · Conjunctive satisfiability with functions and inequalities · Minimum axiom set · First order subsumption · Second order instantiation
Théorie des automates et des langages formels Théorie des automates
Finite state automaton inequivalence · Two-way finite state automaton non-emptiness · Linear bounded automaton acceptance · Quasi-realtime automaton acceptance · Non-erasing stack automaton acceptance · Finite state automata intersection · Reduction of incompletely specified automata · Minimum inferred finite state automaton
Langages formels
Regular expression inequivalence · Minimum inferred regular expression · Reynolds covering for context-free grammars · Covering for linear grammars · Structural inequivalence for linear grammars · Regular grammar inequivalence · Non-LR(K) context-free grammar · Etol grammar non-emptiness · Context-free programmed language membership · Quasi-real-time language membership · Etol language membership · Context-sensitive language membership · Tree transducer language membership