class of problem is associated with Rank revealing QR factorizations and D optimal experimental design. Minimal addition chains for sequences. The complexity of minimal addition chains for individual numbers is unknown. Modal logic S5-Satisfiability Pancake sorting distance problem for strings Solving two-variable quadratic polynomials over the integers. Given positive integers , find positive integers such that Second order instantiation Serializability of database histories Set cover (also called minimum cover problem) This is equivalent, by transposing the incidence matrix, to the hitting set problem. Set packing Set splitting problem Scheduling to minimize weighted completion time Block Sorting (Sorting by Block Moves) Sparse approximation Variations of the Steiner tree problem. Specifically, with the discretized Euclidean metric, rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric. Three-dimensional Ising model See also Existential theory of the reals#Complete problems Karp's 21 NP-complete problems List of PSPACE-complete problems Reduction (complexity) Notes References General . This book is a classic, developing the theory, then cataloguing many NP-Complete problems. Specific problems Further information available online at Richard Kaye's Minesweeper pages. External links A compendium of NP optimization problems Graph of NP-complete Problems Mathematics-related lists Lists of problems