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

Dyer, M. E.; Frieze, A. M.

SIAM J. Comput. 17, No. 5, 967-974 (1988).

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

MSC:

68Q25	Analysis of algorithms and problem complexity
52Bxx	Polytopes and polyhedra

Keywords:

computational complexity; #P-easy; volume; polyhedron; convex hull; linear inequalities; #P-hard