Equivalent Problems
Although the canonical exact cover problem involves a collection of subsets of a set X, the logic does not depend on the presence of subsets containing elements. An "abstract exact cover problem" arises whenever there is a binary relation between two sets P and Q and the goal is to select a subset P* of P such that each element in Q is related to exactly one element in P*. In general, the elements of P represent choices and the elements of Q represent "exactly one" constraints on those choices.
More formally, given a binary relation R P × Q between sets P and Q, one can call a subset P* of P an "abstract exact cover" of Q if each element in Q is R -1-related to exactly one element in P*. Here R -1 is the inverse of R.
In general, R -1 restricted to Q × P* is a function from Q to P*, which maps each element in Q to the unique element in P* that is R-related that element in Q. This function is onto, unless P* contains the "empty set," i.e., an element which isn't R-related to any element in Q.
In the canonical exact cover problem, P is a collection of subsets of X, Q is the set X, R is the binary relation "contains" between subsets and elements, and R -1 restricted to Q × P* is the function "is contained in" from elements to selected subsets.
Read more about this topic: Exact Cover
Famous quotes containing the words equivalent and/or problems:
“Accountability in friendship is the equivalent of love without strategy.”
—Anita Brookner (b. 1938)
“We are all adult learners. Most of us have learned a good deal more out of school than in it. We have learned from our families, our work, our friends. We have learned from problems resolved and tasks achieved but also from mistakes confronted and illusions unmasked. . . . Some of what we have learned is trivial: some has changed our lives forever.”
—Laurent A. Daloz (20th century)