Equality cases of the Alexandrov–Fenchel inequality are not in the polynomial hierarchy
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
2024-01-01
|
| Series: | Forum of Mathematics, Pi |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S2050508624000209/type/journal_article |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 2050-5086 |