Liste de problèmes NP-complets

Un article de Wikipédia, l'encyclopédie libre.

Aller à : Navigation, Rechercher

Ceci est une liste des problèmes NP-complets les plus connus en théorie de la complexité, exprimés sous la forme d'un problèmes de la 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-Completeness ^[1]. Ils sont présentés ici suivant les mêmes ordre et organisation.

Sommaire [masquer] 1 Géométrie algorithmique 2 Théorie des graphes 2.1 Couverture et découpage en partitions 2.2 Sous-graphes et super-graphes 2.3 Tri des sommets 2.4 Morphismes 2.5 Divers 3 Conception de réseau 3.1 Arbres couvrants 3.2 Coupures et connexité 3.3 Routage 3.4 Flux 3.5 Divers 4 Ensembles et partitions 4.1 Couverture, échantillonnage et partition 4.2 Ensembles avec poids assignés 5 Stokage d'information et accès 5.1 Stokage d'information 5.2 Compression et représentation 5.3 Bases de données 6 Ordonnancement dans les systèmes d'exploitation 6.1 Sur un processeur unique 6.2 Sur plusieurs processeurs 6.3 Ordonnancement manufacturier 6.4 Divers 7 Programmation mathématique 8 Algèbre et théorie des nombres 8.1 Problèmes de divisibilité 8.2 Résolubilité d'équations 8.3 Divers 9 Jeux 10 Logique 10.1 Logique propositionnelle 10.2 Divers 11 Théorie des automates et des langages formels 11.1 Théorie des automates 11.2 Langages formels 12 Optimisation de programme 12.1 Génération de code 12.2 Programmes et schémas 13 Divers 14 Références 15 Voir aussi 16 Liens externes

Géométrie algorithmique [modifier]

Article détaillé : géométrie algorithmique.

• Triangulation avec poids minimal d'un ensemble de points dans le plan ^[2]
• Tester si un arbre peut être représenté comme un arbre couvrant minimum euclidien
• Reconnaissance d'un graphe d'un disque unitaire (c'est le graphe d'intersection du cercle unitaire dans le plan)^[3]
• 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 AS par un déplacement rigide et sans collision de S et tel que S et AS sont connectés. ^[4]

Théorie des graphes [modifier]

Article détaillé : théorie des graphes.

Couverture et découpage en partitions [modifier]

Articles détaillés : couverture (théorie des graphes) et partition (mathématiques).

Couverture des sommets · Ensemble dominant · Nombre domatique · Coloration de graphe à k couleurs · Nombre achromatique · Triangle monochromatique · Ensemble de sommets à rétroaction · Ensemble d'arcs à rétroaction · Ensembles de côtés à rétroaction partielle · Pairage maximal minimum · 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 stocastique de poids maximum en deux étapes · Couverture par cliques · Couverture par sous-graphes bipartis complets

Sous-graphes et super-graphes [modifier]

Vous venez d'apposer le bandeau {{Demande de traduction}} du Projet:Traduction/*/Demandes.

Veuillez créer (exemple détaillé) la sous-page qui assurera le suivi du processus de traduction en cliquant sur Projet:Traduction/Liste de problèmes NP-complets.

Puis suivez les instructions fournies sur la page ainsi créée.

Clique

· Independent set · Induced subgraph with property Pi · Induced connected subgraph with property Pi · Induced path · Balanced complete bipartite subgraph · Bipartite subgraph · Degree-bounded connected subgraph · Planar subgraph · Edge-subgraph · Transitive subgraph · Uniconnected subgraph · Minimum k-connected subgraph · Cubic subgraph · Minimum equivalent digraph · Hamiltonian completion · Interval graph completion · Path graph completion

Tri des sommets [modifier]

Cycle hamiltonien · Cycle hamiltonien orienté · Hamiltonian path · Bandwidth · Directed bandwidth · Optimal linear arrangement · Directed optimal linear arrangement · Minimum cut linear arrangement · Rooted tree arrangement · Directed elimination ordering · Elimination degree sequence

Morphismes [modifier]

Article détaillé : morphisme.

Isomorphisme de sous-graphe · Plus grand sous-graphe commun · Maximum subgraph matching · Graph contractability · Graph homomorphism · Digraph D-morphism

Divers [modifier]

Path with forbidden pairs · Multiple choice matching · Graph Grundy numbering · Kernel · K-closure · Intersection graph basis · Path distinguishers · Metric dimension · Nesetril-Rödl dimension · Threshold number · Oriented diameter · Weighted diameter

Conception de réseau [modifier]

Article détaillé : réseau.

Arbres couvrants [modifier]

Article détaillé : arbre couvrant.

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 · Steiner tree · Geometric Steiner tree · Cable Trench Problem

Coupures et connexité [modifier]

Graph partitioning · Acyclic partition · Max weight cut · Minimum cut into bounded sets · Biconnectivity augmentation · Strong connectivity augmentation · Network reliability · Network survivability · Multiway Cut · Minimum k-cut

Routage [modifier]

Article détaillé : routage.

Bottleneck traveling salesman · Chinese postman for mixed graphs · Euclidean traveling salesman · K most vital arcs · Kth shortest path · Metric traveling salesman · Longest circuit · Longest path · Prize Collecting Traveling Salesman · Rural Postman · Shortest path in general networks · Shortest weight-constrained path · Stacker-crane · Time constrained traveling salesman feasibility · Problème du voyageur de commerce · Vehicle Routing

Flux [modifier]

Article détaillé : flux (réseau).

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 [modifier]

Quadratic assignment problem · Minimizing dummy activities in PERT networks · Constrained triangulation · 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 · Metric k-center

Ensembles et partitions [modifier]

Articles détaillés : ensemble et partition (mathématiques).

Couverture, échantillonnage et partition [modifier]

3-dimensional matching · Couverture exacte · Set packing · Set splitting · Set cover · Minimum test set · Set basis · Hitting set · Intersection pattern · Comparative containment · 3-matroid intersection

Ensembles avec poids assignés [modifier]

Partition · Somme de sous-ensembles · Produit de sous-ensembles · 3-partition · Numerical 3-dimensional matching · Numerical matching with target sums · Expected component sum · Minimum sum of squares · Kth largest subset · Kth largest m-tuple

Stokage d'information et accès [modifier]

Stokage d'information [modifier]

Article détaillé : 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 [modifier]

Article détaillé : compression de données.

Shortest common supersequence · Shortest common superstring . Longest common subsequence problem for the case of arbitrary (i.e., not a priori fixed) number of input sequences even in the case of the binary alphabet · Bounded post correspondence problem · Hitting string · Sparse matrix compression · Consucutive ones submatrix · Consecutive ones matrix partition · Consecutive ones matrix augmentation · Consecutive block minimization · Consecutive sets · 2-dimensional consecutive sets · String-to-string correction · 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 [modifier]

Article détaillé : base de données.

Minimum cardinality key · Additional key · Prime attribute name · Boyce-Codd normal form violation · Conjunctive query foldability · Conjunctive boolean query · Tableau equivalence · Serializability of database histories · Safety of database transaction systems · Consistency of database frequency tables · Safety of file protection systems

Ordonnancement dans les systèmes d'exploitation [modifier]

Article détaillé : ordonnancement dans les systèmes d'exploitation.

Sur un processeur unique [modifier]

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 [modifier]

Multiprocessor scheduling · Precedence constrained scheduling · Resource constrained scheduling · Scheduling with individual deadlines · Preemptive scheduling · Scheduling to minimize weighted completion time

Ordonnancement manufacturier [modifier]

Open-shop scheduling · Flow-shop scheduling · No-wait flow-shop scheduling · Two-processor flow-shop with bounded buffer · Job-shop scheduling

Divers [modifier]

Timetable design · Staff scheduling · Production planning · Deadlock avoidance

Programmation mathématique [modifier]

Article détaillé : programmation mathématique.

Programmation linéaire · Programmation linéaire 0-1 · Programmation quadratique (NP-hard dans certains cas; dans P lorsque convexe) · 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 [modifier]

Articles détaillés : algèbre et théorie des nombres.

Problèmes de divisibilité [modifier]

Article détaillé : 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 [modifier]

Quadratic diophantine equations · Algebraic equations over GF[2] · Root of modulus 1 · Number of roots for a product polynomial · Periodic solution recurrence relation

Divers [modifier]

Permanent evaluation · Cosine product integration · Equilibrium point · Unification with commutative operators · Unification for finitely presented algebras · Integer expression membership

Jeux [modifier]

Article détaillé : jeu.

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 · Light Up · Slither Link . Kakuro · Clickomania · Tetris · Mastermind . Masyu . Lemmings

Logique [modifier]

Article détaillé : logique.

Logique propositionnelle [modifier]

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 [modifier]

Quantified boolean formulas · 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 [modifier]

Théorie des automates [modifier]

Article détaillé : 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 [modifier]

Article détaillé : 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

Optimisation de programme [modifier]

Génération de code [modifier]

Register sufficiency · Feasible register assignment · Register sufficiency for loops · Code generation on a one-register machine · Code generation with unlimited registers · Code generation for parallel assignments · Code generation with address expressions · Code generation with unfixed variable locations · Ensemble computation · Microcode bit optimization

Programmes et schémas [modifier]

Article détaillé : programmation informatique.

Inequivalence of programs with arrays · Inequivalence of programs with assignments · Inequivalence of finite memory programs · Inequivalence of loop programs without nesting · Inequivalence of simple functions · Strong inequivalence of Ianov schemes · Strong inequivalence for monadic recursion · Non-containment for free B-schemes · Non-freedom for loop-free program schemes · Programs with formally recursive procedures

Divers [modifier]

Cyclic ordering · Non-liveness of free choice Petri nets · Reachability for 1-conservative Petri nets · Finite function generation · Permutation generation · Decoding of linear codes · Shapley-Shubik voting power · Clustering · Randomization test for matched pairs · Maximum likelihood ranking · Matrix domination · Matrix cover · Simply deviated disjunction · Decision tree · Minimum weight and/or graph solution · Fault detection in logic circuits · Fault detection in directed graphs · Fault detection with test points