About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Information and Computation
Paper
Uniform generation of script N℘-witnesses using an script N℘-oracle
Abstract
A uniform generation procedure for script N℘ is an algorithm that, given any input in a fixed script N℘ -language, outputs a uniformly distributed script N℘ -witness for membership of the input in the language. We present a uniform generation procedure for script N℘ that runs in probabilistic polynomial time with an script N℘ -oracle. This improves upon results of M. Jerrum et al. (1986, Theoret. Comput. Sci. 43, 169-188), which either require a Σ2p oracle or obtain only almost uniform generation. Our procedure utilizes ideas originating in the works of M. Sipser, and L. Stockmeyer (respectively, 1983, in Proceedings of the 15th Annual Symposium on the Theory of Computing, ACM, New York), and Jerrum et al. (1986). © 2000 Academic Press.