<p>Consider the space $\mathbb{Q}^n$.</p>

<p>A convex polyhedron is defined, equivalently, by a system of linear (in)equalities (with integer coefficients) or by a system of generators: vertices, and in case of unbounded polyhedra, rays and lines. (In some of the literature, these two descriptions are called H-representation and V- or W-representation.)</p>

<p>Are there recent results on the complexity of the problem of checking the equivalence of a constraint and a generator representation?</p>

<p>What I know:</p>

<ol>
<li>Checking whether a polyhedron defined by constraints is included in another defined by generators (even if the second one is bounded) is co-NP-complete (Freund &amp; Orlin, 1985).</li>
<li>Enumerating all vertices of an unbounded polyhedron (note: I have not discussed the other generators) is NP-hard. If I understand this result correctly, checking, given a list of constraints and a list of vertices, whether the list of vertices is exhaustive, is co-NP-complete (Khachiyan et al., 2008).</li>
</ol>

CC BY-SA 3.0
2017-05-17T14:00:39.023Z
If a $\Pi_2^\text{p}$ upper bound is sufficient for your purposes, you could formulate this decision problem as a $\Pi_2$-sentence in FO($\mathbb{R}, +, \le$), which is decidable in $\Pi_2$, shown by Eduardo D. Sontag: Real Addition and the Polynomial Hierarchy. Inf. Process. Lett. 20(3): 115-120 (1985).
Christoph Haase
CC BY-SA 3.0
2017-05-17T14:54:22.550Z
It is in co-NP. The difficult part is the lower bound.
David Monniaux
CC BY-SA 3.0
2017-05-18T03:41:14.937Z
Doesn't problem 2 reduce to checking equivalence of V-rep and H-rep, hence the latter is also coNP complete?
Joshua Grochow
CC BY-SA 3.0
2017-05-18T04:22:16.270Z
@JoshuaGrochow not exactly because their reduction produces unbounded polyhedra, but the list contains only vertices, not rays. They say that the complexity of enumerating both rays and vertices is open.
Sasho Nikolov
<co.combinatorics><polytope>
Complexity of checking the equivalence of constraints and generator descriptions of convex polyhedra
David Monniaux
# Complexity of checking the equivalence of constraints and generator descriptions of convex polyhedra

(Asked by: username_0 on 2017-05-17)

Consider the space $\mathbb{Q}^n$.

A convex polyhedron is defined, equivalently, by a system of linear (in)equalities (with integer coefficients) or by a system of generators: vertices, and in case of unbounded polyhedra, rays and lines. (In some of the literature, these two descriptions are called H-representation and V- or W-representation.)

Are there recent results on the complexity of the problem of checking the equivalence of a constraint and a generator representation?

What I know:

1. Checking whether a polyhedron defined by constraints is included in another defined by generators (even if the second one is bounded) is co-NP-complete (Freund & Orlin, 1985).
2. Enumerating all vertices of an unbounded polyhedron (note: I have not discussed the other generators) is NP-hard. If I understand this result correctly, checking, given a list of constraints and a list of vertices, whether the list of vertices is exhaustive, is co-NP-complete (Khachiyan et al., 2008).

**Tags:** co.combinatorics, polytope
> **Comments:**
> **username_1**: If a $\Pi_2^\text{p}$ upper bound is sufficient for your purposes, you could formulate this decision problem as a $\Pi_2$-sentence in FO($\mathbb{R}, +, \le$), which is decidable in $\Pi_2$, shown by Eduardo D. Sontag: Real Addition and the Polynomial Hierarchy. Inf. Process. Lett. 20(3): 115-120 (1985).  
> **username_0**: It is in co-NP. The difficult part is the lower bound.  
> **username_2**: Doesn't problem 2 reduce to checking equivalence of V-rep and H-rep, hence the latter is also coNP complete?  
> **username_3**: @JoshuaGrochow not exactly because their reduction produces unbounded polyhedra, but the list contains only vertices, not rays. They say that the complexity of enumerating both rays and vertices is open.  

---

## 0 answers

