  Describing the equality conditions of the Alexandrov--Fenchel inequality has
been a major open problem for decades. We prove that in the case of convex
polytopes, this description is not in the polynomial hierarchy unless the
polynomial hierarchy collapses to a finite level. This is the first hardness
result for the problem, and is a complexity counterpart of the recent result by
Shenfeld and van Handel (arXiv:archive/201104059), which gave a geometric
characterization of the equality conditions. The proof involves Stanley's order
polytopes and employs poset theoretic technology.
