|Input:||Polytope P in H-description|
|Output:||The volume of P|
|Status (general):||#P-hard, FPRAS|
|Status (fixed dim.):||Polynomial time|
Dyer and Frieze  showed that the general problem is
#P-hard (and #P-easy as well). Dyer, Frieze, and
Kannan  found a Fully Polynomial Randomized
Approximation Scheme (FPRAS) for the problem, i.e., a
family (Ae)e>0 of randomized
algorithms, where, for each e> 0, Ae
computes a number Ve with the property that the
probability of (1-e) vol(P) £ Ve £ (1+e) vol(P) is at least 3/4, and the
running times of the algorithms Ae are bounded by a
polynomial in the input size and 1/e.
For fixed dimension, one can first compute all vertices of P (see Problem 1) and its face lattice (see Problem 5) both in polynomial time. Then one can construct some triangulation (see Problem 11) of P (e.g., its barycentric subdivision) in polynomial time and compute the volume of P as the sum of the volumes of the (maximal) simplices in the triangulation.
The complexity status of the analogue problem with the polytope specified by a V-description is the same.