Here are some of the more commonly known problems that are NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

 when expressed as decision problem

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...

s. This list is in no way comprehensive (there are more than 3000 known NP-complete problems). Most of the problems in this list are taken from Garey and Johnson's seminal book Computers and Intractability: A Guide to the Theory of NP-Completeness, and are here presented in the same order and organization.

Covering and partitioning

• Vertex cover
  Vertex cover
  In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....
  
  
• Dominating set, a.k.a. domination number

NP-complete special cases include the edge dominating set

Edge dominating set

In graph theory, an edge dominating set for a graph G =  is a subset D ⊆ E such that every edge not in D is adjacent to at least one edge in D. An edge dominating set is also known as a line dominating set...

 problem, i.e., the dominating set problem in line graphs. NP-complete variants include the connected dominating set

Connected dominating set

In graph theory, a connected dominated set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph.-Definitions:A connected dominating set of a graph G is a set D of vertices with two properties:...

 problem.

• Domatic partition, a.k.a. domatic number
• Graph coloring
  Graph coloring
  In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
  
  , a.k.a. chromatic number
• Partition into cliques

This is the same problem as coloring

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...

 the complement of the given graph.

• Complete coloring
  Complete coloring
  In graph theory, complete coloring is the opposite of harmonious coloring in the sense that it is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper...
  
  , a.k.a. achromatic number
• Monochromatic triangle
  Monochromatic triangle
  The monochromatic triangle problem is a decision problem that is known to be NP-complete.Input: An n-node undirected graph G with node set V and edge set E....
  
  
• Feedback vertex set
  Feedback vertex set
  In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph....
  
  
• Feedback arc set
  Feedback arc set
  In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph . One way to do this is simply to drop edges from the graph to break the cycles...
  
  
• Partial feedback edge set
• Minimum maximal independent set a.k.a. minimum independent dominating set

NP-complete special cases include the minimum maximal matching problem, which is essentially equal to the edge dominating set

Edge dominating set

In graph theory, an edge dominating set for a graph G =  is a subset D ⊆ E such that every edge not in D is adjacent to at least one edge in D. An edge dominating set is also known as a line dominating set...

 problem (see above).

• Partition
  Graph partition
  In mathematics, the graph partition problem is defined on data represented in the form of a graph G= , with V vertices and E edges, such that it is possible to partition G into smaller components with specific properties. For instance, a k-way partition divides the vertex set into k smaller...
  
   into triangles
• Partition
  Graph partition
  In mathematics, the graph partition problem is defined on data represented in the form of a graph G= , with V vertices and E edges, such that it is possible to partition G into smaller components with specific properties. For instance, a k-way partition divides the vertex set into k smaller...
  
   into isomorphic
  Graph isomorphism
  In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
  
   subgraphs
• Partition
  Graph partition
  In mathematics, the graph partition problem is defined on data represented in the form of a graph G= , with V vertices and E edges, such that it is possible to partition G into smaller components with specific properties. For instance, a k-way partition divides the vertex set into k smaller...
  
   into Hamiltonian subgraphs
• Partition
  Graph partition
  In mathematics, the graph partition problem is defined on data represented in the form of a graph G= , with V vertices and E edges, such that it is possible to partition G into smaller components with specific properties. For instance, a k-way partition divides the vertex set into k smaller...
  
   into forests
• Partition
  Graph partition
  In mathematics, the graph partition problem is defined on data represented in the form of a graph G= , with V vertices and E edges, such that it is possible to partition G into smaller components with specific properties. For instance, a k-way partition divides the vertex set into k smaller...
  
   into perfect matchings
• Two-stage maximum weight stochastic matching 
• Clique covering problem
  Clique cover
  In computational complexity theory, finding a minimum clique cover is a graph-theoretical NP-complete problem. The problem was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems"....
  
  
• Berth allocation problem
  Berth allocation problem
  The berth allocation problem is an NP-complete problem in operations research, regarding the allocation of berth space for vessels in container terminals....
  
   
• Covering by complete bipartite subgraphs
  Bipartite dimension
  In the mathematical field of graph theory, the bipartite dimension of a graph G =  is the minimum number of bicliques, that is, complete bipartite subgraphs, needed to cover all edges in E. A collection of bicliques covering all edges in G is called a biclique edge cover, or sometimes...
  
  
• Grundy number
• Rank coloring
  Cycle rank
  In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close adigraph is to a directed acyclic graph , in the sense that a DAG has...
  
   a.k.a. cycle rank
• Treewidth

Subgraphs and supergraphs

• Clique
  Clique problem
  In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
  
  
• Independent set
• Induced subgraph with property Π 
• Induced connected subgraph with property Π 
• Induced path
  Induced path
  In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the...
  
  
• 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
  Hamiltonian completion
  The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian.The problem is clearly NP-hard in general case...
  
  
• Interval graph completion
• Path graph completion

Vertex ordering

• Hamiltonian circuit
  Hamiltonian path problem
  In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph . Both problems are NP-complete...
  
  
• Directed Hamiltonian circuit
• Hamiltonian path
  Hamiltonian path problem
  In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph . Both problems are NP-complete...
  
  
• Bandwidth
• Directed bandwidth
• Optimal linear arrangement
• Directed optimal linear arrangement
• Minimum cut linear arrangement
• Rooted tree arrangement
• Directed elimination ordering
• Elimination degree sequence
• Pathwidth, or, equivalently, interval thickness, and vertex separation number

Iso- and other morphisms

• Subgraph isomorphism
  Subgraph isomorphism problem
  In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H....
  
  
• Largest common subgraph
  Maximum common subgraph isomorphism problem
  In complexity theory, maximum common subgraph-isomorphism is an optimization problem that is known to be NP-hard. The formal description of the problem is as follows:Maximum common subgraph-isomorphism...
  
  
• Maximum subgraph matching
• Graph contractibility
• Graph homomorphism
  Graph homomorphism
  In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices.-Definitions:...
  
  
• Digraph D-morphism

Miscellaneous

• Path with forbidden pairs
• Multiple choice matching
• Graph Grundy numbering
• Kernel
• K-closure
• Intersection graph basis
• Path distinguishers
• Metric dimension
  Metric dimension (graph theory)
  In graph theory, the metric dimension of a graph G is the minimum number of vertices in a subset S of G such that all other vertices are uniquely determined by their distances to the vertices in S...
  
  
• Nešetřil–Rödl dimension
• Threshold number
• Oriented diameter
• Weighted diameter

Spanning trees

• Degree-constrained spanning tree
• Minimum degree spanning tree
  Minimum degree spanning tree
  In graph theory, for a connected graph G, a spanning tree T is a subgraph of G with the least number of edges that still spans G. A number of properties can be proved about T. T is acyclic, has edges where V is the number of vertices in G etc....
  
  
• Maximum leaf spanning tree
• Minimum k-spanning tree
• Shortest total path length spanning tree
  Shortest total path length spanning tree
  In computer science, the shortest total path length spanning tree is, given an n-node undirected graph G; positive integer B, does there exist a spanning tree T of G such that the sum over all pairs of nodes u and v of the length of the path between u and v in T is no greater than B?...
  
  
• Bounded diameter spanning tree
• Capacitated spanning tree
• Geometric capacitated spanning tree
• Optimum communication spanning tree
  Steiner tree
  The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.The...
  
  
• Isomorphic spanning tree
• Kth best spanning tree
• Bounded component spanning forest
• Multiple choice branching
• Steiner tree
  Steiner tree
  The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.The...
  
  
• Geometric Steiner tree
  Steiner tree
  The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.The...
  
  
• Cable Trench Problem
  Steiner tree
  The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.The...
  
  
• Minimum touching tree/Minimum length corridor

Cuts and connectivity

• Graph partitioning
• Acyclic partition
• Maximum cut
  Maximum cut
  For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the max-cut problem.The problem can be stated simply as follows...
  
  
• Minimum bounded cut (minimum cut into bounded sets)
• Biconnectivity augmentation
• Strong connectivity augmentation
• Network reliability
• Network survivability
• Normalized cut
• Multiway cut
• Minimum k-cut
  Minimum k-cut
  In mathematics, the minimum k-cut, is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to k connected components. These edges are referred to as k-cut. The goal is to find the minimum-weight k-cut...
  
  
• k-vital edges

Routing problems

• Bottleneck traveling salesman
• Chinese postman for mixed graphs
• Euclidean traveling salesman
• k-Chinese postman
• K most vital arcs
• Kth shortest path problem
• Metric traveling salesman
• Longest circuit problem
• Longest path problem
  Longest path problem
  In the mathematical discipline of graph theory, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices...
  
  
• Prize collecting traveling salesman
• Rural postman
• Shortest path
  Shortest path problem
  In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
  
   in general networks
• Shortest weight-constrained path
• Stacker-crane
• Time constrained traveling salesman feasibility
• Traveling salesman problem
• Vehicle routing problem
  Vehicle routing problem
  The vehicle routing problem is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. Proposed by Dantzig and Ramser in 1959, VRP is an important problem in the fields of transportation, distribution and logistics...
  
  
• Capacitated arc routing problem

Flow problems

• 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
• Maximum flow network interdiction problem
• Unsplittable multicommodity flow

Miscellaneous

• Quadratic assignment problem
  Quadratic assignment problem
  The quadratic assignment problem is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems....
  
  
• Minimizing dummy activities in PERT networks
• Constrained triangulation
• Intersection graph
  Intersection graph
  In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
  
   for segments on a grid
• Edge embedding on a grid
• Geometric connected dominating set
• Minimum broadcast time problem
• Min-max multicenter
• Min-sum multicenter
• Uncapacitated Facility Location
  Facility location
  Facility location, also known as location analysis, is a branch of operations research and computational geometry concerning itself with mathematical modeling and solution of problems concerning optimal placement of facilities in order to minimize transportation costs, avoid placing hazardous...
  
  
• Metric k-center
  Metric k-center
  In graph theory, the metric k-center, is a combinatorial optimization problem studied in theoretical computer science. Given n cities with specified distances, one wants to build k warehouses in different cities and minimize the distance of the farthest city from its closest warehouse...
  
  

Graph Drawing

Graphs

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

 occur frequently in everyday applications, and are used to model a lot of often huge data. Such examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (see e.g. Facebook

Facebook

Facebook is a social networking service and website launched in February 2004, operated and privately owned by Facebook, Inc. , Facebook has more than 800 million active users. Users must register before using the site, after which they may create a personal profile, add other users as...

 or LinkedIn

LinkedIn

LinkedIn is a business-related social networking site. Founded in December 2002 and launched in May 2003, it is mainly used for professional networking. , LinkedIn reports more than 120 million registered users in more than 200 countries and territories. The site is available in English, French,...

). Therefore, even when all information is available in the form of a graph, it is important to have good ways of visualizing the data in order to make sense of it and extract interesting features, and this is what makes graph drawing

Graph drawing

Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...

 important.

• Rectilinear planarity testing
• Upward planarity testing
• Upward sphericity testing
• Maximum upward planar subgraph computation for embedded digraphs

Covering, hitting, and splitting

• 3-dimensional matching
  3-dimensional matching
  In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching to 3-uniform hypergraphs...
  
  
• Exact cover
• Set packing
  Set packing
  Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems.Suppose we have a finite set S and a list of subsets of S...
  
  
• Set splitting
• Set cover
  Set cover problem
  The set covering problem is a classical question in computer science and complexity theory.It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms...
  
  
• Minimum test set
• Set basis
  Bipartite dimension
  In the mathematical field of graph theory, the bipartite dimension of a graph G =  is the minimum number of bicliques, that is, complete bipartite subgraphs, needed to cover all edges in E. A collection of bicliques covering all edges in G is called a biclique edge cover, or sometimes...
  
  
• Hitting set
• Intersection pattern
• Comparative containment
• 3-matroid intersection

Weighted set problems

• Partition
  Partition problem
  In computer science, the partition problem is an NP-complete problem. The problem is to decide whether a given multiset of integers can be partitioned into two "halves" that have the same sum...
  
  
• Subset sum
• Subset product
• 3-partition
• Numerical 3-dimensional matching
  Numerical 3-dimensional matching
  Numerical 3-dimensional matching is a strongly NP-complete decision problem. It is given by three multisets of integers X, Y and Z, each containing k elements, and a bound b...
  
  
• Numerical matching with target sums
• Expected component sum
• Minimum sum of squares
• Kth largest subset
• Kth largest m-tuple

Data storage

• Bin packing
  Bin packing problem
  In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used....
  
  
• Dynamic storage allocation
• Pruned trie space minimization
• Expected retrieval cost
• Rooted tree storage assignment
• Multiple copy file allocation
• Capacity assignment

Compression and representation

• Shortest common supersequence
  Shortest common supersequence
  This shortest common supersequence problem is closely related to the longest common subsequence problem. Given two sequences X = and Y = , a sequence U = is a common supersequence of X and Y if U is a supersequence of both X and Y...
  
  
• Shortest common superstring
• Longest common subsequence problem
  Longest common subsequence problem
  The longest common subsequence problem is to find the longest subsequence common to all sequences in a set of sequences . Note that subsequence is different from a substring, see substring vs. subsequence...
  
   for the case of arbitrary (i.e., not a priori fixed) number of input sequences. (In contrast, the alphabet size is immaterial as long as it is greater than one.)
• Bounded Post correspondence problem
• Hitting string
• Sparse matrix
  Sparse matrix
  In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
  
   compression
• Consecutive ones submatrix
• Consecutive ones matrix partition
• Consecutive ones matrix augmentation
• Consecutive block minimization
• Consecutive sets
• 2-dimensional consecutive sets
• String-to-string correction
  String-to-string correction problem
  The string-to-string correction problem refers to the minimum number of edit operations necessary to change one string into another. A single edit operation may be changing a single symbol of the string into another, deleting, or inserting a symbol...
  
  
• 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
• Adaptive block-size compression

Database problems

• Minimum cardinality key
• Additional key
• Prime attribute name
• Boyce-Codd normal form
  Boyce-Codd normal form
  Boyce–Codd normal form is a normal form used in database normalization. It is a slightly stronger version of the third normal form...
  
   violation
• Conjunctive query foldability
• Conjunctive Boolean query
• Tableau equivalence
• Serializability
  Serializability
  In concurrency control of databases, transaction processing , and various transactional applications , both centralized and distributed, a transaction schedule is serializable, has the serializability property, if its outcome In concurrency control of databases, transaction processing (transaction...
  
   of database histories
• Safety of database transaction systems
• Consistency of database frequency tables
• Safety of file protection systems

Sequencing on one processor

• Job sequencing
• 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

Multiprocessor scheduling

• Multiprocessor scheduling
  Multiprocessor scheduling
  In computer science, multiprocessor scheduling is an NP-complete optimization problem. The problem statement is: "Given a set J of jobs where job ji has length li and a number of processors mi, what is the minimum possible time required to schedule all jobs in J on m processors such that none...
  
  
• Precedence constrained scheduling
• Resource constrained scheduling
• Scheduling with individual deadlines
• Preemptive scheduling
• Scheduling to minimize weighted completion time

Shop scheduling

• Open-shop scheduling
• Flow Shop Scheduling Problem
  Flow Shop Scheduling Problem
  Flow Shop Scheduling Problems, or FSPs, are a class of scheduling problems with a work shop or group shop in which the flow control shall enable an appropriate sequencing for each job and for processing on a set of machines or with other resources 1,2,...,m in compliance with given processing orders...
  
  
• No-wait Flow Shop Scheduling
• Two-processor Flow Shop with bounded buffer
• Job-shop scheduling

Miscellaneous

• Timetable design
• Staff scheduling
• Production planning
• Deadlock avoidance

Mathematical programming

• Integer linear programming
• 0-1 linear programming
• Quadratic programming
  Quadratic programming
  Quadratic programming is a special type of mathematical optimization problem. It is the problem of optimizing a quadratic function of several variables subject to linear constraints on these variables....
  
   (NP-hard in some cases, P if convex)
• Cost-parametric linear programming
• Feasible basis extension
• Open hemisphere
• K-relevancy
• Traveling salesman polytope non-adjacency
• Knapsack
  Knapsack problem
  The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as...
  
  
• Integer knapsack
• Continuous multiple choice knapsack
• Partially ordered knapsack
• Generalized assignment problem
  Generalized assignment problem
  In applied mathematics, the maximum generalized assignment problem is a problem in combinatorial optimization. This problem is a generalization of the assignment problem in which both tasks and agents have a size...
  
  
• Comparative vector inequalities
• Selecting a maximum volume submatrix – Problem of selecting the best conditioned subset of a larger m x n matrix. This class of problem is associated with Rank revealing QR factorizations and D optimal experimental design.
• Sparse approximation
  Sparse approximation
  Sparse approximation is the problem of finding a signal or vector estimate with sparseness property, that is having a small number of nonzero elements, that satisfies a system of equations....
  
  

Divisibility problems

• Quadratic congruences
• Simultaneous incongruences
• Simultaneous divisibility of linear polynomials
• Comparative divisibility
• Exponential expression divisibility
• Non-divisibility of a product polynomial
• Non-trivial greatest common divisor
  Greatest common divisor
  In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
  
  

Solvability of equations

• Quadratic Diophantine equation
  Diophantine equation
  In mathematics, a Diophantine equation is an indeterminate polynomial equation that allows the variables to be integers only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for all equations...
  
  s
• Algebraic equations over GF(2)
  GF(2)
  GF is the Galois field of two elements. It is the smallest finite field.- Definition :The two elements are nearly always called 0 and 1, being the additive and multiplicative identities, respectively...
  
  ; or over any finite field
  Finite field
  In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
  
  .
• Root of modulus
  Modulus
  Modulus may refer to:* Modulus a genus of small sea snails* Modulus , a formal product of places of a number field* The absolute value of a real or complex number...
  
   1
• Number of roots for a product polynomial
• Periodic solution recurrence relation
• Non-linear univariate polynomials over GF[2ⁿ], n the length of the input. Indeed over any GF[qⁿ].

Miscellaneous

• Permanent evaluation
• Cosine product integration
• Equilibrium point
• Unification with commutative
  Commutativity
  In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
  
   operators
• Unification for finitely presented algebras
• Integer expression membership
• Minimal addition chain

Games and puzzles

• Alternating hitting set
• Alternating maximum weighted matching
• Annihilation
• Battleship
  Battleship (puzzle)
  The Battleship puzzle is a logic puzzle based on the Battleship guessing game...
  
  
• Bulls and Cows
  Bulls and cows
  Bulls and Cows -- also known as Cows and Bulls or Pigs and Bulls or Bulls and Cleots -- is an old code-breaking paper and pencil game for two players, predating the similar commercially-marketed board game Master Mind....
  
  , marketed as Master Mind
  Mastermind (board game)
  Mastermind or Master Mind is a code-breaking game for two players. The modern game with pegs was invented in 1970 by Mordecai Meirowitz, an Israeli postmaster and telecommunications expert, but the game resembles an earlier pencil and paper game called bulls and cows that may date back a century or...
  
  
• Clickomania (SameGame)
  SameGame
  is a computer puzzle game featuring tile removal originally released under the name Chain Shot! in 1985 by Kuniaki Moribe . It has since been ported to numerous computer platforms.-History:...
  
  
• Cross Sums
  Cross Sums
  Kakuro or Kakkuro is a kind of logic puzzle that is often referred to as a mathematical transliteration of the crossword. Kakuro puzzles are regular features in many math-and-logic puzzle publications in the United States...
  
  
• Crossword
  Crossword
  A crossword is a word puzzle that normally takes the form of a square or rectangular grid of white and shaded squares. The goal is to fill the white squares with letters, forming words or phrases, by solving clues which lead to the answers. In languages that are written left-to-right, the answer...
  
   puzzle construction
• Eternity II
  Eternity II puzzle
  The Eternity II puzzle, aka E2 or E II, is a puzzle competition which was released on 28 July 2007.The competition ended at noon on the 31st of December 2010.It was published by Christopher Monckton, and is marketed and copyrighted by TOMY UK Ltd...
  
  
• Fillomino
  Fillomino
  Fillomino is a type of logic puzzle published by Nikoli. Other published titles for the puzzle include Allied Occupation. As of 2005, three books consisting entirely of Fillomino puzzles have been published by Nikoli.-Rules:...
  
  
• Flood-It
• FreeCell
  FreeCell
  FreeCell is a solitaire-based card game played with a 52-card standard deck. It is fundamentally different from most solitaire games in that nearly all deals can be solved...
  
  
• Heyawake
  Heyawake
  Heyawake is a binary-determination logic puzzle published by Nikoli. As of 2011, four books consisting entirely of Heyawake puzzles have been published by Nikoli...
  
  
• Instant Insanity
  Instant Insanity
  The "Instant Insanity" puzzle consists of four cubes with faces colored with four colors . The object of the puzzle is to stack these cubes in a column so that each side of the stack shows each of the four colors...
  
  
• Kakuro
• Lemmings
• Light Up
  Light Up
  Light Up , also called Akari, is a binary-determination logic puzzle published by Nikoli. As of 2011, three books consisting entirely of Light Up puzzles have been published by Nikoli.-Rules:...
  
  
• Masyu
  Masyu
  Masyu is a type of logic puzzle designed and published by Nikoli. The purpose of its creation was to present a puzzle that uses no numbers or letters and yet retains depth and aesthetics.-Rules:...
  
  
• Minesweeper Consistency Problem
• Nurikabe
  Nurikabe
  Nurikabe is a binary determination puzzle named for an invisible wall in Japanese folklore that blocks roads and delays foot travel...
  
  
• Paint by numbers (Nonogram)
• Rabin games
• Sift
• Slither Link
  Slither Link
  Slitherlink is a logic puzzle developed by publisher Nikoli.-Rules:...
  
  
• Square-tiling
• Sudoku
  Sudoku
  is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid contains all of the digits from 1 to 9...
  
  
• Tetris
  Tetris
  Tetris is a puzzle video game originally designed and programmed by Alexey Pajitnov in the Soviet Union. It was released on June 6, 1984, while he was working for the Dorodnicyn Computing Centre of the Academy of Science of the USSR in Moscow, Russian Soviet Federative Socialist Republic...
  
  
• Variable partition truth assignment
• Verbal arithmetic
  Verbal arithmetic
  Verbal arithmetic, also known as alphametics, cryptarithmetic, crypt-arithmetic, cryptarithm or word addition, is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters. The goal is to identify the value of each letter...
  
  

Propositional logic

Propositional logic problems, in particular satisfiability problems and their variants, are of particular practical interest because many practical problems can be solved by expressing them as satisfiability problems, and then using efficient SAT solvers to obtain an exact solution quickly.

• Boolean satisfiability
• 3-satisfiability
• Not-all-equal 3SAT
• One-in-three 3SAT
  One-in-three 3SAT
  In computational complexity theory, one-in-three 3SAT is an NP-complete problem. The problem is a variant of the 3-satisfiability problem . Like 3SAT, the input instance is a collection of clauses, where each clause consists of exactly three literals, and each literal is either a variable or its...
  
  
• Maximum 2-Satisfiability
• Generalized satisfiability
• Non-tautology
• Minimum equivalent disjunctive normal form
  Disjunctive normal form
  In boolean logic, a disjunctive normal form is a standardization of a logical formula which is a disjunction of conjunctive clauses. As a normal form, it is useful in automated theorem proving. A logical formula is considered to be in DNF if and only if it is a disjunction of one or more...
  
   for a given truth table
• Truth-functionally complete connectives
• Planar-3SAT
• Monotone-3SAT

Miscellaneous

• Modal logic
  Modal logic
  Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...
  
   S5-Satisfiability
• Negation-free logic
• Conjunctive satisfiability with functions and inequalities
• Minimum axiom set
• First order subsumption
• Second order instantiation
  Universal instantiation
  In logic universal instantiation is an inference from a truth about each member of a class of individuals to the truth about a particular individual of that class. It is generally given as a quantification rule for the universal quantifier but it can also be encoded in an axiom...
  
  

Automata theory

• Reduction of incompletely specified automata
• Minimum inferred finite state automaton

Formal languages

• Minimum inferred regular expression
• Reynolds covering for context-free grammars
• Non-LR(k)
  LR parser
  In computer science, an LR parser is a parser that reads input from Left to right and produces a Rightmost derivation. The term LR parser is also used; where the k refers to the number of unconsumed "look ahead" input symbols that are used in making parsing decisions...
  
   context-free grammar
• Context-free programmed language membership
• Quasi-real-time language membership

Computational geometry

Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...

• Testing whether a tree
  Tree (graph theory)
  In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
  
   may be represented as Euclidean minimum spanning tree
  Euclidean minimum spanning tree
  The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane , where the weight of the edge between each pair of points is the distance between those two points...
  
  
• Unit disk graph
  Unit disk graph
  In geometric graph theory, a unit disk graph is the intersection graph of a family of unit circles in the Euclidean plane. That is, we form a vertex for each circle, and connect two vertices by an edge whenever the corresponding circles cross each other....
  
   recognition (Unit disk graphs are intersection graphs of circles of unit radius in the plane)
• Many motion planning
  Motion planning
  Motion planning is a term used in robotics for the process of detailing a task into discrete motions....
  
   among polygonal obstacles in the plane are NP-hard.
  • Planar partitioning into connected subassemblies: Given a set A of non-overlapping (but possibly touching) polygons in the plane, decide if there is a proper subset S of A that can be separated from A\S by a collision-free rigid motion of S, and such that both S and A\S are connected.
• Art gallery problem
  Art gallery problem
  The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards which together can observe the whole gallery...
  
   and its variations.

Code generation

• Register sufficiency
• Feasible register assignment
• Register sufficiency for loops
• Code generation
  Code generation
  In computer science, code generation is the process by which a compiler's code generator converts some intermediate representation of source code into a form that can be readily executed by a machine ....
  
   on a one-register
  Processor register
  In computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...
  
   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

Programs and schemes

• 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

Miscellaneous

• Sorting by Reversals
• Sorting by Transpositions
• Block Sorting (Sorting by Block Moves)
• Pancake sorting
  Pancake sorting
  Pancake sorting is a variation of the sorting problem in which the only allowed operation is to reverse the elements of some prefix of the sequence. Unlike a traditional sorting algorithm, which attempts to sort with the fewest comparisons possible, the goal is to sort the sequence in as few...
  
  
• Cyclic ordering
• Non-liveness of free choice Petri nets
• Reachability for 1-conservative Petri nets
• Finite function generation
• Permutation generation
• Decoding of linear code
  Linear code
  In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...
  
  s
• Shapley–Shubik power index
• 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 graph
  Directed graph
  A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
  
  s
• Fault detection with test point
  Test point
  A test point is a location within an electronic circuit that is used to either monitor the state of the circuitry or to inject test signals. Test points have two primary uses:...
  
  s
• Three-dimensional Ising model
  Ising model
  The Ising model is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables called spins that can be in one of two states . The spins are arranged in a graph , and each spin interacts with its nearest neighbors...
  
  

External links

• Graph of NP-complete Problems

-->