# Volume computation of special polytopes

I'm interested in computing the volume of a special class of $$\mathcal{H}$$-polytopes and the complexity of doing so.

I know that in general it is #P-hard to compute the volume of $$\mathcal{H}$$ -polytopes, which doesn't exclude the existence of a subclass of $$\mathcal{H}$$-polytopes where a volume computation could be done efficiently.

Analysing a particular subclass of polytopes I realized that order polytopes belong to this subclass. The volume computation of order polytopes corresponds to computing the number of linear extensions in an underlying poset, which is known to be #P-complete.

Does that imply that volume computation in my special class of polytopes is #P-hard, too?

My thought is yes, because a polynomial time algorithm for my special class would solve the problem of computing the number of linear extensions efficiently. I'm not that familar with complexity theory, so I'm not sure if this argument suffices.

Edit: The special class of polytopes are defined by $$P=\lbrace x\in\mathbb{R}^n : Ax\leq b\rbrace$$, such that the normal vectors (rows of A) are elements from the set

$$R_n:=\lbrace e_i-e_j: i,j\in \lbrace 1,...,n\rbrace, i\neq j\rbrace \cup \lbrace \pm e_1,...,\pm e_n\rbrace$$,

where $$e_1,...e_n$$ are the canonical unit vectors.

Order polytopes are defined by a partially ordered set $$(PO,<_{PO})$$ with $$PO=\lbrace a_1,...,a_n\rbrace$$ and

$$O(PO)=\lbrace x\in\mathbb{R}^n : 0\leq x_i\leq 1$$ for all $$i=1,...,n$$ and $$x_i\leq x_j$$ if $$a_i<_{PO} a_j$$ in $$PO\rbrace$$.

Hence their normal vectors are precisely from the set $$R_n$$.

Edit 2: With $$\mathcal{H}$$-polytopes I mean polytopes given in their halfspace representation (intersection of halfspaces $$P=\lbrace x\in\mathbb{R}^n : Ax\leq b\rbrace$$).

• Were you going to tell us what your special class of polytopes was? – Andrej Bauer Sep 11 '19 at 19:37