One of the most important results in computational complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

 was Stephen Cook

Stephen Cook

Stephen Arthur Cook is a renowned American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity...

's 1971 demonstration of the first (practically relevant) 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...

 problem, the boolean satisfiability problem

Boolean satisfiability problem

In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...

. In 1972, Richard Karp

Richard Karp

Richard Manning Karp is a computer scientist and computational theorist at the University of California, Berkeley, notable for research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto...

 took this idea a leap forward with his landmark paper, "Reducibility Among Combinatorial Problems", in which he showed that 21 diverse combinatorial

Combinatorics

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

 and graph theoretical

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...

 problems, each infamous for its computational intractability, are NP-complete.

By revealing that a large number of problems important to researchers are NP-complete, Karp motivated the study of NP

NP (complexity)

In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...

, NP-completeness, and the now-famous P = NP question.

The problems

Karp's 21 problems, many with their original names, are shown below, with the nesting indicating the direction of the reductions used. For example, 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...

 was shown to be NP-complete by reducing EXACT COVER to KNAPSACK.

• SATISFIABILITY
  Boolean satisfiability problem
  In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
  
  : the boolean satisfiability problem for formulas in conjunctive normal form
  Conjunctive normal form
  In Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...
  
   (often referred to as SAT)
  • 0-1 INTEGER PROGRAMMING
  • 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....
    
     (see also independent set problem)
    • 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...
      
      
    • VERTEX COVER
      • SET COVERING
        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...
        
        
      • FEEDBACK NODE 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...
        
        
      • DIRECTED HAMILTON 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...
        
         (Karp's name, now usually called DIRECTED HAMILTONIAN CIRCUIT)
        • UNDIRECTED HAMILTON 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...
          
           (Karp's name, now usually called UNDIRECTED HAMILTONIAN CIRCUIT)
  • SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE (equivalent to 3-SAT)
    • CHROMATIC NUMBER
      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...
      
       (also called the Graph Coloring Problem
      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...
      
      )
      • CLIQUE COVER
        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"....
        
        
      • EXACT COVER
        • HITTING SET
        • 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...
          
          
        • 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...
          
          
        • 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...
          
           (Karp's definition of Knapsack is closer to Subset sum)
          • JOB SEQUENCING
          • 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...
            
            
            • MAX 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...
              
              

As time went on it was discovered that many of the problems can be solved efficiently if restricted to special cases, or can be solved within any fixed percentage of the optimal result. However, David Zuckerman showed in 1996 that every one of these 21 problems has a constrained optimization version that is impossible to approximate within any constant factor unless P = NP, by showing that Karp's approach to reduction generalizes to a specific type of approximability reduction.