Computing the exact volume of a polytope given in half space representation seems to be NP-hard. One paper I found proved it is hard for rational coefficients. (However, the paper itself was behind a paywall, so I don't know what exactly they did.)


What are the weakest restrictions under which the problem is still difficult? How many dimensions are required if all coefficients are rational? If the polytope is given as $Ax \le b$, can $b$ be integer valued? Is there a high enough dimension so that $A$ can be integer valued?




---


Motivation is, I want to prove that another problem is NP-hard and want to achieve that by reducing polytope volume calculation to it.




---


EDIT: The paper [Büeler, Enge, and Fukuda - Exact volume computations for polytopes: A practical study](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.7953) linked at <https://mathoverflow.net/a/989/167596> cited the older paper [Dyer and Frieze - On the complexity of computing the volume of a polyhedron](https://epubs.siam.org/doi/10.1137/0217060).


Possibly the linked paper itself implies answers to my question, but not that I can tell.



Exact volume calculation of a polytope is NP hard under which restrictions?
Not sure answering ones own question is common practice here, but I did get the information I was looking for out of that paper:


*Dyer, M. E.; Frieze, A. M.*, [**On the complexity of computing the volume of a polyhedron**](http://dx.doi.org/10.1137/0217060), SIAM J. Comput. 17, No. 5, 967-974 (1988). [ZBL0668.68049](https://zbmath.org/?q=an:0668.68049). states


"[...] THEOREM 1. Computing vol (P(A, b)) is #P-hard, even when A is totally uni-
modular. [...]"


If I'm not mistaken this implies the problem is hard for integer valued $A$ and $b$. (if $b\_i = p / q$ we can simply multiply row $i$ by $q$)


They do however state that the problem is solvable in polynomial time for a fixed number of dimensions.


