On the Polyhedral Decision Problem
Andrew Chi-Chih Yao, Ronald L. Rivest · SIAM Journal on Computing · 1980
Computational problems sometimes can be cast in the following form: Given a point ${\bf x}$ in $R^n $, determine if ${\bf x}$ lies in some fixed polyhedron. In this paper we give a general lower bound to the complexity of such problems, showing that $\frac{1}{2}\log _2 f_s $ linear comparisons are needed in the worst case, for any polyhedron with $f_s$s-dimensional faces. For polyhedra with abundant faces, this leads to lower bounds nonlinear in n, the number of variables.