ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMATE COUNTING.:
Reports tagged with Approximate Counting.:
TR98-032 | 10th June 1998
Mihir Bellare, Oded Goldreich, Erez Petrank

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

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 ... more >>>



ISSN 1433-8092 | Imprint