Exact cover
Karp (1972) introduces the name ‘exact cover’ for the following decision problem:
INPUT: Family Sj of subsets of a set ui, i=1,2,…,t
PROPERTY: There is a subfamily Th ⊆ Sj such that the sets Th are disjoint and ∪Th = ∪Sj = ui, i=1,2,…,t
(The problem being to determine, for an arbitrary input, whether it possesses the property.) Karp goes on to prove that this problem is NP-complete, using a reduction from chromatic number, which has a reduction from satisfiability with at most three literals per clause, which in turn has a reduction from satisfiability, which he proves is NP-complete directly.
( Instances of this problem often arise in the solution of combinatorial problems … )