On the Polyhedral Decision Problem

Computational problems sometimes can be cast in the following form: Given a point x in Rⁿ, determine if x lies in some fixed polyhedron. In this paper we give a general lower bound to the complexity of such problems, showing that 1/2log ₂ fₛ linear comparisons are needed in the worst case, for any polyhedron with fₛs-dimensional faces. For polyhedra with abundant faces, this leads to lower bounds nonlinear in n, the number of variables.