In mathematics, given a collection of subsets of a set X, an exact hitting set X* is a subset of X such that each subset in contains exactly one element in X*. One says that each subset in is hit by exactly one element in X*.
In computer science, the exact hitting set problem is a decision problem to find an exact hitting set or else determine none exists.
The exact hitting set problem is an abstract exact cover problem. In the notation above, P is the set X, Q is a collection of subsets of X, R is the binary relation "is contained in" between elements and subsets, and R -1 restricted to Q × P* is the function "contains" from subsets to selected elements.
Whereas an exact cover problem involves selecting subsets and the relation "contains" from subsets to elements, an exact hitting set problem involves selecting elements and the relation "is contained in" from elements to subsets. In a sense, an exact hitting set problem is the inverse of the exact cover problem involving the same set and collection of subsets.
Read more about this topic: Exact Cover
Famous quotes containing the words exact, hitting and/or set:
“Reading maketh a full man; conference a ready man; and writing an exact man.”
—Francis Bacon (1561–1626)
“Can we not teach children, even as we protect them from victimization, that for them to become victimizers constitutes the greatest peril of all, specifically the sacrifice—physical or psychological—of the well-being of other people? And that destroying the life or safety of other people, through teasing, bullying, hitting or otherwise, “putting them down,” is as destructive to themselves as to their victims.”
—Lewis P. Lipsitt (20th century)
“I never can hear a crowd of people singing and gesticulating, all together, at an Italian opera, without fancying myself at Athens, listening to that particular tragedy, by Sophocles, in which he introduces a full chorus of turkeys, who set about bewailing the death of Meleager.”
—Edgar Allan Poe (1809–1845)