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 compensation for a death sentence is knowledge of the exact hour when one is to die. A great luxury, but one that is well earned.”
—Vladimir Nabokov (1899–1977)
“The toddler’s wish to please ... is a powerful aid in helping the child to develop a social awareness and, eventually, a moral conscience. The child’s love for the parent is so strong that it causes him to change his behavior: to refrain from hitting and biting, to share toys with a peer, to become toilet trained. This wish for approval is the parent’s most reliable ally in the process of socializing the child.”
—Alicia F. Lieberman (20th century)
“No annual training or muster of soldiery, no celebration with its scarfs and banners, could import into the town a hundredth part of the annual splendor of our October. We have only to set the trees, or let them stand, and Nature will find the colored drapery,—flags of all her nations, some of whose private signals hardly the botanist can read,—while we walk under the triumphal arches of the elms.”
—Henry David Thoreau (1817–1862)