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:
“Since we are assured that the all-wise Creator has observed the most exact proportions of number, weight and measure in the make of all things, the most likely way therefore to get any insight into the nature of those parts of the Creation which come within our observation must in all reason be to number, weigh and measure.”
—Stephen Hales (1677–1761)
“I feel all dead inside. I’m backed up in a dark corner and I don’t know who’s hitting me!”
—Jay Dratler, U.S. screenwriter, Bernard Schoenfeld, and Henry Hathaway. Bradford Galt (Mark Stevens)
“I set out on this ground, which I suppose to be self evident, “that the earth belongs in usufruct to the living”: that the dead have neither powers nor rights over it.”
—Thomas Jefferson (1743–1826)