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:
“Years ago we discovered the exact point, the dead center of middle age. It occurs when you are too young to take up golf and too old to rush up to the net.”
—Franklin Pierce Adams (1881–1960)
“It is not [the toddler’s] job yet to consider other people’s feelings, he has to come to terms with his own first. If he hits you and you hit him back to “show him what it feels like,” you will have given a lesson he is not ready to learn. He will wail as if hitting was a totally new idea to him. He makes no connections between what he did to you and what you then did to him; between your feelings and his own.”
—Penelope Leach (20th century)
“He that has his chains knocked off, and the prison doors set open to him, is perfectly at liberty, because he may either go or stay, as he best likes; though his preference be determined to stay, by the darkness of the night, or illness of the weather, or want of other lodging. He ceases not to be free, though the desire of some convenience to be had there absolutely determines his preference, and makes him stay in his prison.”
—John Locke (1632–1704)