Karp's 21 NP-complete problems

Angol

Satisfiability: the boolean satisfiability problem for formulas in conjunctive normal form (often referred to as SAT)
- 0–1 integer programming (A variation in which only the restrictions must be satisfied, with no optimization)
- Clique (see also independent set problem)
  - set packing
  - Vertex cover
    - Set covering
    - Feedback node set
    - Feedback arc set
    - Directed Hamilton circuit (Karp's name, now usually called Directed Hamiltonian cycle)
      - Undirected Hamilton circuit (Karp's name, now usually called Undirected Hamiltonian cycle)
- Satisfiability with at most 3 literals per clause (equivalent to 3-SAT)
  - Chromatic number (also called the Graph Coloring Problem)
    - clique cover problem
    - exact cover problem
      - hitting set problem
      - Steiner tree
      - 3-dimensional matching problem
      - Knapsack (Karp's definition of Knapsack is closer to Subset sum)
        Job sequencing
        
        Partition
        Max cut