I would like to draw your attention to the 2002 survey by Volker Kaibel and Marc Pfetsch, "Some Algorithmic Problems in Polytope Theory," [arXiv:math/0202204v1][1], which contains this on p.6: <br /> ![KP Problems][2] <br /> As you probably know, an $\cal{H}$-description is by halfspaces, whereas a $\cal{V}$-description is by vertices. Reference [20] is: R. M. Freund and J. B. Orlin, "On the complexity of four polyhedral set containment problems," *Math. Program.*, 33 (1985), pp. 139–145. Reference [17] is B. C. Eaves and R. M. Freund, "Optimal scaling of balls and polyhedra," *Math. Program.*, 23 (1982), pp. 138–147. [1]: http://arxiv.org/abs/math/0202204 [2]: https://i.sstatic.net/zNXOG.jpg