8
$\begingroup$

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

Your Answer

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

Browse other questions tagged or ask your own question.