On the complexity of computing the volume of a polyhedron. (English) Zbl 0668.68049

The paper considers the problem of computing the volume of a polyhedron in n dimensions given either as a convex hull of its vertices or as a set of linear inequalities (both representations use only rational numbers). It is shown that this problem is #P-hard for both representations, i.e., it is at least as hard as computing the permanent of a matrix. On the other hand, in the vertex-based case the #P-easiness of the volume problem is shown, i.e., one can compute the volume in polynomial time using a #P-complete oracle. Note that the volume problem is not in class #P. As for the facet-based case, the #P-easiness is proven of computing V such that \(| V-Vol| <\epsilon\) where Vol is the actual volume. Some other results clarifying the volume problem complexity further are also given. See also L. G. Khachiyan, Usp. Mat. Nauk 44, No.3(267), 179-180 (1989).
Reviewer: N.Kornunko


68Q25 Analysis of algorithms and problem complexity
52Bxx Polytopes and polyhedra
Full Text: DOI