Liste de probl猫mes NP-complets
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-Completeness[1]. Ils sont pr茅sent茅s ici suivant les m锚mes ordre et organisation.
G茅om茅trie algorithmique
- Triangulation avec poids minimal (en) 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 de disques unitaires (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 A\S par un d茅placement rigide et sans collision de S et tel que S et A\S sont connect茅s[4].
Th茅orie des graphes
Couverture et d茅coupage en partitions
Couverture par sommets 路 Ensemble dominant 路 Nombre domatique 路 Coloration de graphe 脿 k couleurs 路 Nombre achromatique 路 Triangle monochromatique (en) 路 Coupe-cycles de sommets (feedback vertex set) 路 Ensemble d'arcs 脿 r茅troaction 路 Ensembles de c么t茅s 脿 r茅troaction partielle 路 Pairage maximal minimum (en) 路 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 cliques (en) 路 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 路 Chemin induit (en) 路 Sous-graphe biparti 茅quilibr茅 complet 路 Sous-graphe biparti 路 Sous-graphe connexe maximum de degr茅 born茅 路 Sous-graphe planaire 路 Sous-graphe maximum avec des ar锚tes communes (en) 路 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 路 dimension m茅trique (en) 路 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 路 k-coupure minimale (en)
Routage
Bottleneck traveling salesman (en) 路 Probl猫me du postier chinois 路 Voyageur de commerce euclidien 路 K arcs les plus vitaux 路 Kth shortest path (en) 路 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 de l'assignement quadratique (en) 路 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 路 Set splitting (en) 路 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 supers茅quence commune (en) . 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 路 String-to-string correction (en) 路 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 路 Conjunctive boolean query (en) 路 Tableau equivalence 路 Serializability of database histories 路 Safety of database transaction systems 路 Consistency of database frequency tables 路 Safety of file protection systems
Ordonnancement
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
Multiprocessor scheduling (en) 路 Precedence constrained scheduling 路 Resource constrained scheduling 路 Scheduling with individual deadlines 路 Preemptive scheduling 路 Scheduling to minimize weighted completion time
Ordonnancement manufacturier
Open-shop scheduling (en) 路 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 路 Optimisation lin茅aire en variables 0-1 (en) 路 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 路 Approximation creuse (en)
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[5] 路 Algebraic equations over GF[2] 路 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 路 Light Up (en) 路 Slither Link 路 Kakuro 路 Clickomania (en) 路 Tetris[6] 路 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
Optimisation de programme
G茅n茅ration de code
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
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
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
R茅f茅rences
- M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman. 1983. (ISBN 0-7167-1045-5).
- Minimum Weight Triangulation is NP-Hard, 22nd SCG (2006)
- H. Breu and D. G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998
- "Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165.
- (en) Kenneth Manders et Leonard Adleman, 芦 NP-complete decision problems for quadratic polynomials 禄, Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76, ACM Press,鈥?/span> , p. 23鈥?9 (DOI 10.1145/800113.803627, lire en ligne, consult茅 le )
- beaut茅 math茅matique en chronologie Futura Sciences
- Erich Friedman. "Pearl Puzzles are NP-Complete". In preparation. 2002. .
- Paul E. Dunne. An Annotated List of Selected NP-complete Problems. Universit茅 de Liverpool, D茅partement d'informatique, COMP202.
- Pierluigi Crescenzi, Viggo Kann, Magn煤s Halld贸rsson, Marek Karpinski et Gerhard Woeginger. A compendium of NP optimization problems. KTH NADA. Stockholm.