Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910984328708096 |
|---|---|
| author | Chan, Swee Hong Pak, Igor |
| author_facet | Chan, Swee Hong Pak, Igor |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_05764 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy Chan, Swee Hong Pak, Igor Combinatorics Computational Complexity Computational Geometry Discrete Mathematics Metric Geometry 05A20, 06A07, 52A40 (Primary) 11A55, 52A39, 68Q15, 68Q17, 68R05 (Secondary) 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. |
| title | Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy |
| topic | Combinatorics Computational Complexity Computational Geometry Discrete Mathematics Metric Geometry 05A20, 06A07, 52A40 (Primary) 11A55, 52A39, 68Q15, 68Q17, 68R05 (Secondary) |
| url | https://arxiv.org/abs/2309.05764 |