14
$\begingroup$

Consider a vector of variables $\vec{x}$, and a set of linear constraints specified by $A\vec{x}\leq b$.

Furthermore, consider two polytopes

$$\begin{align*} P_1&=\{(f_1(\vec{x}), \cdots, f_m(\vec{x}))\mid A\vec{x}\leq b\}\\ P_2&=\{(g_1(\vec{x}), \cdots, g_m(\vec{x}))\mid A\vec{x}\leq b\} \end{align*}$$

where $f$'s and $g$'s are affine mappings. Namely, they are of the form $\vec{c}\cdot \vec{x} +d$. (We note that $P_1$ and $P_2$ are polytopes because they are "affine mappings" of the polytope $A\vec{x}\leq b$.)

The question is, how to decide whether $P_1$ and $P_2$ are equal as sets? What's the complexity?

The motivation of the problem is from sensor networks, but it seems to be a lovely (probably basic?) geometry problem. One can solve this in exptime, possibly by enumerating all the vertices of $P_1$ and $P_2$, but is there a better approach?

$\endgroup$
  • 2
    $\begingroup$ What do you mean by two polytopes being equivalent? Three interpretations immediately come to my mind: equal as sets, affinely equivalent, and combinatorially equivalent. The two existing answers assume different interpretations. $\endgroup$ – Tsuyoshi Ito Sep 22 '15 at 1:34
  • $\begingroup$ I mean equal as sets. $\endgroup$ – maomao Sep 22 '15 at 9:38
  • $\begingroup$ Please edit the question to include that clarification. Don't just leave it in the comments. Questions should be self-contained: people shouldn't have to read the comments to understand what you are asking. Thank you. $\endgroup$ – D.W. Sep 23 '15 at 1:23
12
$\begingroup$

I cannot say for sure if you will consider the following approach as better, but from a complexity-theoretic point of view there is a more efficient solution. The idea is to rephrase your question in the first-order theory of the rationals with addition and order. You have that $P_1$ is included in $P_2$ if and only if \begin{align*} \Phi := \forall \vec{x}.\exists \vec{y}.\left( A \cdot \vec{x} \le b \implies \left( A \cdot \vec{y} \le b \wedge \bigwedge_{1\le i\le m} f_i(\vec{x}) = g_i(\vec{y}) \right)\right) \end{align*} is valid. It is clear how to derive equivalence of $P_1$ and $P_2$ in the same way. Now $\Phi$ has a fixed quantifier-alternation prefix, and is consequently decidable in $\Pi_2^\text{P}$, the second level of the polynomial-time hierarchy (Sontag, 1985). I'm pretty confident that it is possible to also prove a matching lower bound, I recall reading somewhere that inclusion between two polytopes is $\Pi_2^\text{P}$-hard.

If you are looking for tool support in order to solve such problems in practice, modern SMT-solvers such as z3 fully support this theory.

$\endgroup$
5
$\begingroup$

The fact that the underlying polytope $Ax \le b$ is the same for $P_1$ and $P_2$ does not matter, unless we know something specific about $A$ and $b$. This is because a general polytope is an affine projection of a simplex (see, for instance, Ziegler's "Lectures for Polytopes", Theorem 2.15). Thus, if $A$ and $b$ encode a simplex, your question is equivalent to asking how hard general polytope isomorphism is. A quick search reveals the following paper by Kaibel and Schwartz On the Complexity of Polytope Isomorphism Problems, where they show that it is Graph Isomorphism hard.

$\endgroup$
  • 2
    $\begingroup$ I don't think this argument works - it ignores the dimension of the simplex given by the quoted theorem. (x is part of the input, so any reduction needs to make sure it's polynomially bounded) $\endgroup$ – Colin McQuillan Oct 1 '15 at 5:38
  • $\begingroup$ Good point! It seems that my claim should still go through, but we have to go inside into the proof in the paper that I cited. Starting with a graph they construct a polytope, such that two graphs are isomorphic if and only if the corresponding polytopes are isomorphic. Their polytopes have a polynomial number of vertices, and their vertex descriptions can be computed in polynomial time. Thus, we can take (A,b) to be a simplex in the dimension that is the number of vertices and f to be the affine projection that gives the polytope that can be obtained from the vertex description. $\endgroup$ – Denis Pankratov Oct 1 '15 at 15:13

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.