# Determine if a polyhedron is a polytope

Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron.

Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly unbounded) polyhedron in $\mathbb{R}^n$ given by $$M \cdot v \geq 0 \quad \textrm{and} \quad v \geq 0.$$ Clearly $0 \in P$ and $P$ is bounded iff $P = \{0\}$. By solving a linear programming problem we can determine if $0$ is the only point in $P$, and so if $P$ is a polytope. Doing this takes $O(m^n)$. Is there a faster way to determine if $P$ is actually a polytope?

-
"Doing this takes $O(m^n)$." Are you sure about this? Linear programs can be solved in time that is polynomial in $m$ and $n$ (see, e.g., the ellipsoid algorithm). –  Gabor Retvari Nov 25 '12 at 23:18