Who am I

風住塵香花已盡,日晚倦梳頭。物事人非事事休,欲語淚先流。聞說雙溪春尚好,也擬泛輕舟。隻恐雙溪舴艋舟,載不動,許多愁。
正文

Liste de problèmes NP-complets

(2007-12-31 07:44:18) 下一個

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.

Sommaire

[masquer]

Géométrie algorithmique [modifier]

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

Théorie des graphes [modifier]

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

Couverture et découpage en partitions [modifier]

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]

Drapeaux

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]

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

[ 打印 ]
閱讀 ()評論 (0)
評論
目前還沒有任何評論
登錄後才可評論.