On the Complexity of Four Polyhedral Set Containment Problems (Classic Reprint)

Excerpt from On the Complexity of Four Polyhedral Set Containment Problems<br/><br/>A nonempty closed convex polyhedron X can be represented either in the form X where (a,b) are given, in which case X is called an H  cell (h for halfspaces), or in the form X where (u,v) are given, in which case X is called a w  cell (w for weighting of points). The computational complexity of many problems related to polyhedra depend on the polyhedral representation as an H-cell or a W-cell. For example, consider a linear program, which can be stated as maximize ctx subject xex, where X is a polyhedron. If X is an H  cell, this is the usual linear program, whose solution time, while polynomial, is by no means negligible. However, if X is represented as a W-cell, the linear programming problem becomes trivial. As another example, consider the problem of testing if xex for a given E, where X is a polyhedron. If X is an H-cell, the problem is trivial, whereas if X is a w-cell, the problem reduces to solving a linear program.