** Abstract: ** A *Uniform Generation procedure* for NP is an algorithm
which given any input in a fixed NP-language, outputs a uniformly distributed
NP-witness for membership of the input in the language. We present a Uniform
Generation procedure for NP that runs in probabilistic polynomial-time with an
NP-oracle. This improves upon results of Jerrum, Valiant and Vazirani, which
either require a Sigma^P_2 oracle or obtain only almost
uniform generation. Our procedure utilizes ideas originating in the works of
Sipser, Stockmeyer, and Jerrum, Valiant and Vazirani.

** Ref:** TR 98-032, Electronic Colloquium on Computational Complexity,
June 1998. Paper available below.

** Paper: ** Available as compressed
postscript, postscript, or
pdf. ( Help if this doesn't work).