Liste de problèmes NP-complets - Définition

Stokage d'information et accès

Stokage 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

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

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

Ensembles et partitions

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

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

Ordonnancement

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 . Resource-constrained scheduling problem

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