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 reality is that zero defects in products plus zero pollution plus zero risk on the job is equivalent to maximum growth of government plus zero economic growth plus runaway inflation.”
—Dixie Lee Ray (b. 1924)
“I respect guilt. It is a dangerous but sometimes useful beast. The guilt that made me want to solve all my children’s problems meant trouble. The guilt that made me question my role in our mother-daughter squabbles proved helpful. Yes, I care about my kids’ problems, and I long to make suggestions. But these days I wait for children to ask for help, and I give it sparingly. Some things can’t be fixed, and I tell them so.”
—Susan Ferraro (20th century)