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)
“While the onset of puberty can vary by as much as six years, every adolescent wants to be right on the 50-yard line, right in the middle of the field. One is always too tall, too short, too thin, too fat, too hairy, too clear-skinned, too early, too late. Understandably, problems of self-image are rampant.”
—Joan Lipsitz (20th century)