9
$\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.