zbMATH — the first resource for mathematics

Hard enumeration problems in geometry and combinatorics. (English) Zbl 0596.68041
The problems: vertices in a polytope, d-dimensional faces of a polytope, facets of a polytope, components of slotted space, acyclic orientations of a graph, 3-colorings of a bipartite graph, and satisfying assignments of an implicative Boolean formula are #P-complete.
Reviewer: J.Ebert

MSC:
 68Q25 Analysis of algorithms and problem complexity 05A15 Exact enumeration problems, generating functions
Full Text:
References:
 [1] Greene, C.; Aigner, M., Acylic orientations (notes), Higher Combinatorics, 65, (1977), D. Reidel, Dordrecht [2] Grünbaum, Branko, Convex polytopes, (1967) · Zbl 0163.16603 [3] Garey, M.; Johnson, D., Computers and intractability, (1979) · Zbl 0411.68039 [4] Hall, Jr., Marshall, An algorithm for distinct representatives, Amer. Math. Monthly, 63, 716, (1956) · Zbl 0074.25004 [5] Every poset has a good comparisonCombinatorica, to appear [6] Provan, S.; Ball, M. O., The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Comput., 12, 777, (1983) · Zbl 0524.68041 [7] Linial, Nathan, The information-theoretic bound is good for merging, SIAM J. Comput., 13, 795, (1984) · Zbl 0548.68065 [8] Stanley, RichardP., Acyclic orientations of graphs, Discrete Math., 5, 171, (1973) · Zbl 0258.05113 [9] Stanley, RichardP., Two combinatorial applications of the Aleksandrov-Fenchel inequalities, J. Combin. Theory Ser. A, 31, 56, (1981) · Zbl 0484.05012 [10] Valiant, L. G., The complexity of computing the permanent, Theoret. Comput. Sci., 8, 189, (1979) · Zbl 0415.68008 [11] Valiant, LeslieG., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, 410, (1979) · Zbl 0419.68082
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.