<p>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 <a href="http://arxiv.org/abs/math/0106093">On the Complexity of Polytope Isomorphism Problems</a>, where they show that it is Graph Isomorphism hard.</p>

CC BY-SA 3.0
2015-10-01T05:38:35.977Z
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)
Colin McQuillan
CC BY-SA 3.0
2015-10-01T15:13:40.810Z
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.
Denis Pankratov
CC BY-SA 3.0
2015-09-21T14:28:54.800Z
2015-09-21T16:36:22.950Z
2015-09-21T16:36:22.950Z
Denis Pankratov
<p>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 (<a href="http://www.sciencedirect.com/science/article/pii/0020019085900766">Sontag, 1985</a>). 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.</p>

<p>If you are looking for tool support in order to solve such problems in practice, modern SMT-solvers such as <a href="https://github.com/Z3Prover/z3">z3</a> fully support this theory.</p>

CC BY-SA 3.0
2015-09-21T13:14:25.940Z
2015-09-21T13:14:25.940Z
Christoph Haase
<p>Consider a vector of variables $\vec{x}$, and a set of <em>linear</em> constraints specified by $A\vec{x}\leq b$.</p>

<p>Furthermore, consider two polytopes</p>

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

<p>where $f$'s and $g$'s are <em>affine</em> 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$.)</p>

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

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

CC BY-SA 3.0
2015-09-22T01:34:47.173Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2015-09-22T09:38:00.563Z
I mean equal as sets.
maomao
CC BY-SA 3.0
2015-09-23T01:23:04.077Z
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.
D.W.
<cc.complexity-theory><linear-algebra><linear-programming><polytope>
Checking equivalence of two polytopes
maomao
# Checking equivalence of two polytopes

(Asked by: username_0 on 2015-09-21)

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?

**Tags:** cc.complexity-theory, linear-algebra, linear-programming, polytope
> **Comments:**
> **username_1**: 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.  
> **username_0**: I mean equal as sets.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_5 on 2015-09-21. Score: 12 | Accepted answer

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](http://www.sciencedirect.com/science/article/pii/0020019085900766)). 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](https://github.com/Z3Prover/z3) fully support this theory.


---

### Answer by username_3 on 2015-09-21. Score: 5

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](http://arxiv.org/abs/math/0106093), where they show that it is Graph Isomorphism hard.

> **Comments:**
> **username_4**: 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)  
> **username_3**: 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.  

---

