cover Mathematical programming 3-partition problem Bin packing problem Bottleneck traveling salesman Uncapacitated facility location problem Flow Shop Scheduling Problem Generalized assignment problem Integer programming. The variant where variables are required to be 0 or 1, called zero-one linear programming, and several other variants are also NP-complete Some problems related to Job-shop scheduling Knapsack problem, quadratic knapsack problem, and several variants Some problems related to Multiprocessor scheduling Numerical 3-dimensional matching Open-shop scheduling Partition problem Quadratic assignment problem Quadratic programming (NP-hard in some cases, P if convex) Subset sum problem Variations on the Traveling salesman problem. The problem for graphs is NP-complete if the edge lengths are assumed integers. The problem for points on the plane is NP-complete with the discretized Euclidean metric and rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric. Vehicle routing problem Formal languages and string processing Closest string Longest common subsequence problem over multiple sequences The bounded variant of the Post correspondence problem Shortest common supersequence over multiple sequences Extension of the string-to-string correction problem Games and puzzles Bag (Corral) Battleship Bulls and Cows, marketed as Master Mind: certain optimisation problems but not the game itself. Edge-matching puzzles Fillomino (Generalized) FreeCell Goishi Hiroi Hashiwokakero Heyawake (Generalized) Instant Insanity Kakuro (Cross Sums) Kingdomino Kuromasu (also known as Kurodoko) LaserTank Lemmings (with a polynomial time limit) Light Up Masyu Minesweeper Consistency Problem (but see Scott, Stege, & van Rooij) Grundy Number of a directed graph. Nonograms Numberlink Nurikabe (Generalized) Pandemic Peg solitaire n-Queens completion Optimal solution for the Rubik's Cube SameGame (Generalized) Set Shakashaka Slither Link on a variety of grids (Generalized) Sudoku Tatamibari Tentai Show Problems related to Tetris Verbal arithmetic Other Berth allocation problem Betweenness Assembling an optimal Bitcoin block. Boolean satisfiability problem (SAT). There are many variations that are also NP-complete. An important variant is where each clause has exactly three literals (3SAT), since it is used in the proof of many other NP-completeness results. Circuit satisfiability problem Conjunctive Boolean query Cyclic ordering Exact cover problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets (this is a matching). Finding the global minimum solution of a Hartree-Fock problem Upward planarity testing Hospitals-and-residents problem with couples Knot genus Latin square completion (the problem of determining if a partially filled square can be completed) Maximum 2-satisfiability Maximum volume submatrix – Problem of selecting the best conditioned subset of a larger matrix. This