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:
“Inter-railers are the ambulatory equivalent of McDonalds, walking testimony to the erosion of French culture.”
—Alice Thompson (b. 1963)
“One of the annoying things about believing in free will and individual responsibility is the difficulty of finding somebody to blame your problems on. And when you do find somebody, it’s remarkable how often his picture turns up on your driver’s license.”
—P.J. (Patrick Jake)