Exact cover

The problem of exact registration (english Exact Cover) is a decision problem in combinatorics. It is one of the 21 classic NP- complete problems, of which Richard M. Karp showed in 1972 that they are NP -complete.

Given a set and a set that contains subsets of, ie, the power set of designated.

Wanted is a subset of whose disjoint union is:

That is, each element in is said to occur in exactly one of the sets in. The quantities thus form an exact cover.

For example, let

The amount

Shows that an exact cover exists.

de