0
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Were you going to tell us what your special class of polytopes was? $\endgroup$ – Andrej Bauer Sep 11 '19 at 19:37
  • 1
    $\begingroup$ Sure, I added more information. $\endgroup$ – sqlman Sep 11 '19 at 20:51
  • $\begingroup$ Could you define what an "H-polytope" is? Also, this may be related to an earlier question of mine: cstheory.stackexchange.com/q/36438 $\endgroup$ – a3nm Sep 11 '19 at 21:26
  • $\begingroup$ 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. $\endgroup$ – sqlman Sep 11 '19 at 21:45
  • $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Sep 12 '19 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.