<p>I'm interested in computing the volume of a special class of <span class="math-container">$\mathcal{H}$</span>-polytopes and the complexity of doing so.</p>

<p>I know that in general it is #P-hard to compute the volume of <span class="math-container">$\mathcal{H}$</span>
-polytopes, which doesn't exclude the existence of a subclass of <span class="math-container">$\mathcal{H}$</span>-polytopes where a volume computation could be done efficiently.</p>

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

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

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

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

<p><span class="math-container">$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$</span>,</p>

<p>where <span class="math-container">$e_1,...e_n$</span> are the canonical unit vectors.</p>

<p>Order polytopes are defined by a partially ordered set <span class="math-container">$(PO,&lt;_{PO})$</span> with <span class="math-container">$PO=\lbrace a_1,...,a_n\rbrace$</span> and</p>

<p><span class="math-container">$O(PO)=\lbrace x\in\mathbb{R}^n : 0\leq x_i\leq 1$</span> for all <span class="math-container">$i=1,...,n$</span> and <span class="math-container">$x_i\leq x_j$</span> if <span class="math-container">$a_i&lt;_{PO} a_j$</span> in <span class="math-container">$PO\rbrace$</span>.</p>

<p>Hence their normal vectors are precisely from the set <span class="math-container">$R_n$</span>.</p>

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

CC BY-SA 4.0
2019-09-11T19:37:49.183Z
Were you going to tell us what your special class of polytopes was?
Andrej Bauer
CC BY-SA 4.0
2019-09-11T20:51:12.283Z
Sure, I added more information.
sqlman
CC BY-SA 4.0
2019-09-11T21:26:06.017Z
Could you define what an "H-polytope" is? Also, this may be related to an earlier question of mine: https://cstheory.stackexchange.com/q/36438
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-09-11T21:45:26.040Z
Also added this information. Could be. My general intuition tells me that all classes of polytopes which contain all order polytopes would be problematic for volume computation, since the volume of order polytopes directly corresponds with the number of linear extensions of partially ordered sets. But as I said, I'm not really familar with complexity theory, specially for counting problems.
sqlman
CC BY-SA 4.0
2019-09-12T00:21:02.077Z
@sqlman That's correct: if your class of polytopes contains all order polytopes, then computing the volume of a polytope in this class is #P-hard, because computing the number of linear extensions of a poset is #P-hard.
Sasho Nikolov
<cc.complexity-theory><computational-geometry>
Volume computation of special polytopes
sqlman
# Volume computation of special polytopes

(Asked by: username_0 on 2019-09-11)

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

**Tags:** cc.complexity-theory, computational-geometry

> **Comments:**
> **username_1**: Were you going to tell us what your special class of polytopes was?  
> **username_0**: Sure, I added more information.  
> **username_2**: Could you define what an "H-polytope" is? Also, this may be related to an earlier question of mine: https://cstheory.stackexchange.com/q/36438  
> **username_0**: Also added this information. Could be. My general intuition tells me that all classes of polytopes which contain all order polytopes would be problematic for volume computation, since the volume of order polytopes directly corresponds with the number of linear extensions of partially ordered sets. But as I said, I'm not really familar with complexity theory, specially for counting problems.  
> **username_3**: @username_0 That's correct: if your class of polytopes contains all order polytopes, then computing the volume of a polytope in this class is #P-hard, because computing the number of linear extensions of a poset is #P-hard.  

---

## 0 answers

