Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-032 | 10th June 1998 00:00

Uniform Generation of NP-witnesses using an NP-oracle.

RSS-Feed




TR98-032
Authors: Mihir Bellare, Oded Goldreich, Erez Petrank
Publication: 12th June 1998 10:15
Downloads: 3514
Keywords: 


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



ISSN 1433-8092 | Imprint