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:
“The secret of genius is to suffer no fiction to exist for us; to realize all that we know; in the high refinement of modern life, in arts, in sciences, in books, in men, to exact good faith, reality, and a purpose; and first, last, midst, and without end, to honor every truth by use.”
—Ralph Waldo Emerson (1803–1882)
“Writing or printing is like shooting with a rifle; you may hit your reader’s mind, or miss it;Mbut talking is like playing at a mark with the pipe of an engine; if it is within reach, and you have time enough, you can’t help hitting it.”
—Oliver Wendell Holmes, Sr. (1809–1894)
“To divide one’s life by years is of course to tumble into a trap set by our own arithmetic. The calendar consents to carry on its dull wall-existence by the arbitrary timetables we have drawn up in consultation with those permanent commuters, Earth and Sun. But we, unlike trees, need grow no annual rings.”
—Clifton Fadiman (b. 1904)