# Which convex polytopes have volumes of polynomial bit-length?

A convex polytope is described as an intersection of halfspaces, given as inequalities between linear combinations of variables with rational coefficients. The volume computation problem for convex polytopes asks, given such a polytope $P$, what is its volume $V(P)$, expressed as a rational number. The size of the input $||P||$ is accounted by writing out the inequalities, with rational numbers written as a pair of numerator and denominator (as binary numbers), and the size of the output $||V(P)||$ is defined in the same way.

It was shown by Lawrence in this paper that there are convex polytopes $P$ for which $||V(P)||$ is exponential in $||P||$, implying, e.g., that the volume computation problem is not in FP$^{\#\mathrm{P}}$. My question is: are there known classes of convex polytopes for which $||V(P)||$ is polynomial in $P$? I know that this is the case, e.g., of simplices; are there other cases?

• slight generalization: those with a polynomial number of vertices – Sasho Nikolov Aug 20 '16 at 14:58
• @SashoNikolov: Thanks, good point! (A reference for it is repository.cmu.edu/cgi/… -- comments at the end of Section 3). But it does not cover all cases of polynomial bit-length. For instance, order polytopes (the polytopes contained in $[0, 1]^n$ defined by inequalities of the form $x_i \leq x_j$) have polynomial bit length (because they can be partitioned in total orders, see math.ucdavis.edu/~lrademac/centroid.pdf lemma 4) but they may not have polynomially many vertices (for the empty order, the cube $[0, 1]^n$ has $2^n$ vertices). – a3nm Aug 23 '16 at 12:30