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).
Improve this question
$\endgroup$
4
  • $\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, 2017 at 14:00
  • 1
    $\begingroup$ It is in co-NP. The difficult part is the lower bound. $\endgroup$
    – David Monniaux
    May 17, 2017 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, 2017 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, 2017 at 4:22

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.