# Complexity of checking the equivalence of constraints and generator descriptions of convex polyhedra

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).
• 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 May 17 '17 at 14:00
• It is in co-NP. The difficult part is the lower bound. – David Monniaux May 17 '17 at 14:54
• Doesn't problem 2 reduce to checking equivalence of V-rep and H-rep, hence the latter is also coNP complete? – Joshua Grochow May 18 '17 at 3:41
• @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 May 18 '17 at 4:22