A geometric inequality and the complexity of computing volume (Q1087143): Difference between revisions

A well-guaranteed separation oracle encoding a bounded convex subset K of Euclidean space \(R^ n\) does the following: i) For any point P it announces P in K or gives a hyperplane separating P from K. ii) It gives, in advance, a fixed ball S containing K and a fixed ball S' contained in K, by giving the center and radius of each ball. The authors use the fact that the volume of the convex hull of any m points of an n-dimensional ball with volume V is at most \(V\cdot m/2^ n\) to prove that no polynomial time algorithm can compute the volume of a convex set K (given by this separation oracle) with less than relative exponential error. In particular, if for some \(c=c(n)<1\) the algorithm can give an estimate \(v_ 0\) for vol(K) up to a factor, i.e., \(c\cdot v_ 0\leq vol(K)\leq v_ 0,\) then its running time is at least \(c\cdot 2^ n-(n+1).\) A lower bound on the complexity of computing the width of K (using the separation oracle) is also deduced: if for some d(n), \(<d(n)<1,\) the algorithm can give an estimate \(w_ 0\) of the width of K such that \(d\cdot w_ 0\leq width(K)\leq w_ 0,\) then its running time is at least \((2d)^ n-(n+1).\)