0
$\begingroup$

Is checking the equivalence of two convex polytopes $p^{s}$ and $p^{t}$ NP-hard?

$p^{s}= CH\{ \cup <p^{s,a_1},...., p^{s,a_m}> \} $ // CH is convex hull computed on union of a polynomial number of polytopes $p^{s,a_i}$

$p^{t}= CH\{ \cup <p^{t,b_1},...., p^{t,b_n}> \}$ // CH is computed on union of a polynomial number of polytopes $p^{t,b_i}$

and

$p^{s,a_i}= \{(x_{i1},.....,x_{ik}) | l_{ij} \leq x_{ij} \leq u_{ij} (j=1,..., k); \sum_{j=1}^k x_{ij} =1 ; l_{ij}, u_{ij} \text{are non-negative rational numbers for} \; j=1,...,k\}$\

and

$p^{t,b_i}= \{(y_{i1},.....,y_{ir}) | l'_{ij} \leq y_{ij} \leq u'_{ij} (j=1,..., r); \sum_{j=1}^r y_{ij} =1 ; l'_{ij}, u'_{ij} \text{are non-negative rational numbers for} \; j=1,...,r\}$\

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ How are your polytopes given? As a system of linear inequalities? By vertices and edges? $\endgroup$ – Brian Borchers Jul 28 '14 at 23:27
  • $\begingroup$ Also, is the dimension $n$ fixed, or do you want asymptotic results in the limit as $n$ goes to $\infty$? $\endgroup$ – Brian Borchers Jul 29 '14 at 3:22
  • $\begingroup$ @Brian: Edited. $\endgroup$ – Star Jul 29 '14 at 13:52
  • $\begingroup$ Yeah, I have no idea about your edited question. With both lower and upper bounds, each $p^{s,a_i}$ can have exponentially many extreme points. Without the upper bounds, though, it's clearly in P because you can enumerate the extreme points of each constituent. $\endgroup$ – tmyklebu Jul 29 '14 at 16:26
4
$\begingroup$

That heavily depends on the representation.

If you're given $P_1$ and $P_2$ as systems of linear inequalities (or, dually, as the convex hull of a finite set of points) with finite precision, you can reduce each linear system (or finite point set) to an irredundant system of linear inequalities by solving linearly many linear programs. Then scale each inequality so that it has a canonical representation, sort them, and check whether the two representations are equal.

If you're given $P_1$ and $P_2$ as systems of linear inequalities with real number coefficients (and you're using a complexity theory that has a notion of "NP-hard" that handles real number computation, like the one derived from the real RAM model), then checking polytope equivalence is exactly as hard as linear programming in said model. (Which is to say that it's still, to my knowledge, an open problem.)

If you allow other primitives (such as "intersect with the integer lattice then take the convex hull") you can make the problem NP-hard.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Every polytopes $P^{s,a_j}$ or $P^{t,b_j}$ is given H-representation. How can I generate H-representation of their convex hull, efficiently? I think this is NP-hard. If you allow for additional variables, then generating the in poly time you can compute an extended formula that its suitable projection gives the convex hull. However, it is not still possible to ensure the equality of two polytopes by checking equality of their extended formulas. $\endgroup$ – Star Aug 18 '15 at 12:25
  • $\begingroup$ Like I said above, I have no idea now that you've edited your question. I certainly don't see an approach that shows this to be soluble in polynomial time. Yes, you can get small extended formulations as you noted, but I don't see how to do anything useful with them. You might try cstheory.stackexchange.com instead. $\endgroup$ – tmyklebu Aug 18 '15 at 13:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.