Uniform generation of NP-witnesses using an NP-oracle

A uniform generation procedure for N P is an algorithm that, given any inpu t in a fixed, N P-language, outputs a uniformly distributed N P-witness for membership of the input in the language, We present a uniform generation p rocedure for N P that runs in probabilistic polynomial time with an N P-ora cle. This improves upon results of M. Jerrum et al. (1986, Theoret. Comput. Sci. 43, 169-188), which either require a Sigma (P)(2) oracle or obtain on ly almost uniform generation, Our procedure utilizes ideas originating in t he works of M. Sipser, and L. Stockmeyer (respectively, 1983, in Proceeding s of the 15th Annual Symposium on the Theory of Computing, ACM, New York), and Jerrum et al. (1986). (C) 2000 Academic Press.