• NP - non-deterministic polynomial
• NPC - NP-Complete

NP Complete Problems

Karp’s 21 NP-Complete Problems

1. 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
       • Exact cover
         • Hitting set
         • Steiner tree
         • 3-dimensional matching
         • Knapsack (Karp’s definition of Knapsack is closer to Subset sum)
           • Job sequencing
           • Partition
             • Max cut