Next: Another proof that BPP
Up: Sabbatical at MIT (1996-1998)
Previous: Eliminating Decryption Errors in
This work presents a probabilistic polynomial-time oracle
machine for uniformly generating instances in an NP-complete
set when given oracle access to the set.
The algorithm utilizes ideas originating in the
works of Sipser, Stockmeyer, and Jerrum, Valiant and Vazirani,
but the presentation is simpler and yields a stronger result.
Comments:
Authored by M. Bellare, O. Goldreich and E. Petrank. Appeared in
- Inform. and Comp., Vol. 163, pages 510-526, 2000.
Oded Goldreich
2003-07-30