Computing the volume is difficult (Q1093369)

Assuming the black box model of a convex set in d-dimensional Euclidean space, algorithms for computing the volume or the width of convex sets are analyzed. Negative results are proved: For every polynomial time algorithm which gives an upper bound \(\overline{vol}\) and a lower bound \(\underline{vol}\) for the volume of a convex set in d-dimensional Euclidean space, there exists a convex set such that the ratio \(\overline{vol}/\underline{vol}\) is greater than \((cd/\log d)^ d\). Similarly, for polynomial time algorithms calculating the width of a convex set (bounds \(\bar w\) and \(\underline w\)), there exists a convex set such that \(\bar w/\underline w>(d/(c \log d))^{1/2}\).