Equality cases of the Alexandrov–Fenchel inequality are not in the polynomial hierarchy

Abstract

Describing the equality conditions of the Alexandrov–Fenchel inequality [Ale37] 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 [SvH23], which gave a geometric characterization of the equality conditions. The proof involves Stanley’s [Sta81] order polytopes and employs poset theoretic technology.

Keywords

• 05A20
• 06A07
• 52A40
• 11A55
• 52A39
• 68Q15
• 68Q17
• 68R05