Hidden subgroup problem: Let G be a group, X a finite set, and f : G → X a function that hides a subgroup H ≤ G. The function f is given via an oracle, which uses O(log |G|+log|X|) bits. Using information gained from evaluations of f via its oracle, determine a generating set for H.
A special case is when X is a group and f is a group homomorphism in which case H corresponds to the kernel of f.
Read more about Hidden Subgroup Problem: Motivation, Algorithms
Famous quotes containing the words hidden and/or problem:
“Yet there is a mystery here and it is not one that I understand: without the sting of otherness, ofeventhe vicious, without the terrible energies of the underside of health, sanity, sense, then nothing works or can work. I tell you that goodness-what we in our ordinary daylight selves call goodness: the ordinary, the decentthese are nothing without the hidden powers that pour forth continually from their shadow sides. Their hidden aspects contained and tempered.”
—Doris Lessing (b. 1919)
“Give a scientist a problem and he will probably provide a solution; historians and sociologists, by contrast, can offer only opinions. Ask a dozen chemists the composition of an organic compound such as methane, and within a short time all twelve will have come up with the same solution of CH4. Ask, however, a dozen economists or sociologists to provide policies to reduce unemployment or the level of crime and twelve widely differing opinions are likely to be offered.”
—Derek Gjertsen, British scientist, author. Science and Philosophy: Past and Present, ch. 3, Penguin (1989)