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:
“The notion that one will not survive a particular catastrophe is, in general terms, a comfort since it is equivalent to abolishing the catastrophe.”
—Iris Murdoch (b. 1919)
“I believe that if we are to survive as a planet, we must teach this next generation to handle their own conflicts assertively and nonviolently. If in their early years our children learn to listen to all sides of the story, use their heads and then their mouths, and come up with a plan and share, then, when they become our leaders, and some of them will, they will have the tools to handle global problems and conflict.”
—Barbara Coloroso (20th century)