×

zbMATH — the first resource for mathematics

Random generation of combinatorial structures from a uniform distribution. (English) Zbl 0597.68056
Summary: The class of problems involving the random generation of combinatorial structures from a uniform distribution is considered. Uniform generation problems are, in computational difficulty, intermediate between classical existence and counting problems. It is shown that exactly uniform generation of ’efficiently verifiable’ combinatorial structures is reducible to approximate counting (and hence, is within the third level of the polynomial hierarchy). Natural combinatorial problems are presented which exhibit complexity gaps between their existence and generation, and between their generation and counting versions. It is further shown that for self-reducible problems, almost uniform generation and randomized approximate counting are inter-reducible, and hence, of similar complexity.

MSC:
68Q25 Analysis of algorithms and problem complexity
68R99 Discrete mathematics in relation to computer science
65C10 Random number generation in numerical analysis
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bach, E., How to generate random integers with known factorisation, (), 184-188
[2] Dixon, J.D.; Wilf, H.S., The random selection of unlabelled graphs, J. algorithms, 4, 205-213, (1983) · Zbl 0532.68064
[3] Erdös, P.; Spencer, J., Probabilistic methods in combinatorics, (1974), Academic Press New York/London · Zbl 0308.05001
[4] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[5] Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. comput., 6, 675-695, (1977) · Zbl 0366.02024
[6] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[7] Karp, R.M.; Luby, M., Monte-Carlo algorithms for enumeration and reliability problems, (), 56-64 · Zbl 0596.90033
[8] Schnorr, C.P., Optimal algorithms for self-reducible problems, (), 322-337
[9] Simon, J., On the difference between one and many, (), 480-491
[10] Sipser, M., A complexity-theoretićapproach to randomness, (), 330-335
[11] Stockmeyer, L., The polynomial-time hierarchy, Theoret. comput. sci., 3, 1-22, (1977) · Zbl 0353.02024
[12] Stockmeyer, L., The complexity of approximate counting, (), 118-126
[13] Valiant, L.G., The complexity of combinatorial computations: an introduction, GI 8 jahrestagung informatik, fachberichte, 18, 326-337, (1978) · Zbl 0399.68062
[14] Valiant, L.G., The complexity of computing the permanent, Theoret. comput. sci., 8, 189-201, (1979) · Zbl 0415.68008
[15] Valiant, L.G.; Vazirani, V.V., NP is as easy as detecting unique solutions, () · Zbl 0621.68030
[16] Wilf, H.S., The uniform selection of free trees, J. algorithms, 2, 204-207, (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.