1
$\begingroup$

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 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.

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

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ If you give a reference for the paper you can't see, probably someone will look at it for you. $\endgroup$
    – Brendan McKay
    Commented Oct 25, 2020 at 3:19
  • $\begingroup$ A related problem is counting lattice polytopes. Its #P-complete (see mit.edu/~har/LRtalk.pdf) to compute Littlewood-Richardson coefficients which are given by counting lattice points in certain polytopes. Perhaps this family is also a source of volume-computation difficulty. See also skew Kostka coefficients. $\endgroup$
    – Per Alexandersson
    Commented Oct 25, 2020 at 18:21

1 Answer 1

Reset to default
1
$\begingroup$

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, SIAM J. Comput. 17, No. 5, 967-974 (1988). ZBL0668.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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .