Liste de problèmes NP-complets
Un article de Wikipédia, l'encyclopédie libre.
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.
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.
· 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
