Liste de problemes NP-complets

Liste de problemes NP-complets

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è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

Géométrie algorithmique

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 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

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

Couverture et découpage en partitions

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 stochastique de poids maximum en deux étapes · Couverture par cliques · Couverture par sous-graphes bipartis complets

Sous-graphes et super-graphes


. Clique maximum . Stable maximum · Ensemble indépendant · 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

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

Morphismes

Article détaillé : Morphisme de graphes.

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

Divers

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

Article détaillé : réseau.

Arbres couvrants

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

Coupures et connexité

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

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 · Problème de tournées de véhicules

Flux

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

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

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

Couverture, échantillonnage et partition

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

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

Stokage d'information

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

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

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

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 · Precedence constrained scheduling · Resource constrained scheduling · Scheduling with individual deadlines · Preemptive scheduling · Scheduling to minimize weighted completion time

Ordonnancement manufacturier

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

Divers

Timetable design · Staff scheduling · Production planning · Deadlock avoidance

Programmation mathématique

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

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

Problèmes de divisibilité

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

Quadratic diophantine equations · 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

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

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

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

Théorie des automates

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

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

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

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

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

  1. 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.
  2. Minimum Weight Triangulation is NP-Hard, 22nd SCG (2006)
  3. H. Breu and D. G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998
  4. "Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165.

Voir aussi

Liens externes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Liste de probl%C3%A8mes NP-complets ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Liste de problemes NP-complets de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • 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èmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

  • 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èmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

  • 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 …   Wikipédia en Français

  • 21 problemes NP-complets de Karp — 21 problèmes NP complets de Karp Les 21 problèmes NP complets de Karp ont marqué une étape importante de l histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes… …   Wikipédia en Français

  • 21 problèmes NP complets de Karp — Les 21 problèmes NP complets de Karp ont marqué une étape importante de l histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes qui sont réductibles entre eux. C …   Wikipédia en Français

  • 21 problèmes NP-complets de Karp — Les 21 problèmes NP complets de Karp ont marqué une étape importante de l histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes qui sont réductibles entre eux. C …   Wikipédia en Français

  • Problemes de Hilbert — Problèmes de Hilbert Lors du deuxième congrès international de mathématiques tenu à Paris en 1900, David Hilbert présenta une liste de problèmes qui tenaient jusqu alors les mathématiciens en échec. Ces problèmes devaient, selon Hilbert, marquer… …   Wikipédia en Français

  • Problèmes de hilbert — Lors du deuxième congrès international de mathématiques tenu à Paris en 1900, David Hilbert présenta une liste de problèmes qui tenaient jusqu alors les mathématiciens en échec. Ces problèmes devaient, selon Hilbert, marquer le cours des… …   Wikipédia en Français

  • Problèmes de Hilbert — Lors du deuxième congrès international des mathématiciens tenu à Paris en 1900, David Hilbert présenta une liste de problèmes qui tenaient jusqu alors les mathématiciens en échec. Ces problèmes devaient, selon Hilbert, marquer le cours des… …   Wikipédia en Français

  • Liste De Logiciels Libres — Les logiciels libres présents sur cette page le sont selon la définition de l article logiciel libre. La plupart des programmes cités ici sont disponibles sous licence GNU GPL ou BSD. Sommaire 1 Système d exploitation 1.1 Famille des GNU/Linux… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”