Next: DES-Like Functions Can Generate
Up: Graduate School (1981-83)
Previous: Graduate School (1981-83)
Two computational problems regarding groups are shown to be NP-hard.
In one, given a set of generators and a target element
in the group formed by them, it is required to find the shortest
sequence of generators that when composed yield the target.
Comments:
Authored by S. Even and O. Goldreich. (Indeed, this was my first paper.) Appeared in
- Journal of Algorithms, vol. 2, pp. 311-313, 1981.
Oded Goldreich
2003-07-30