The diameter of a polytope is a fundamental geometric parameter that plays a crucial role in understanding the efficiency of the simplex method. Despite its central nature, the computational complexity of computing the diameter of a given polytope is poorly understood. Already in 1994, Frieze and Teng [Comp. Compl.] recognized the possibility that this task could potentially be harder than NP-hard, and asked whether the corresponding decision problem is complete for the second stage of the polynomial hierarchy, i.e. $Π^p_2$-complete. In the following years, partial results could be obtained. In a cornerstone result, Frieze and Teng themselves proved weak NP-hardness for a family of custom defined polytopes. Sanità [FOCS18] in a break-through result proved that already for the much simpler fractional matching polytope the problem is strongly NP-hard. Very recently, Steiner and Nöbel [SODA25] generalized this result to the even simpler bipartite perfect matching polytope and the circuit diameter. In this paper, we finally show that computing the diameter of the bipartite perfect matching polytope is $Π^p_2$-hard. Since the corresponding decision problem is also trivially contained in $Π^p_2$, this decidedly answers Frieze and Teng's 30 year old question. Our results also hold when the diameter is replaced by the circuit diameter. As our second main result, we prove that for some $\varepsilon > 0$ the (circuit) diameter of the bipartite perfect matching polytope cannot be approximated by a factor better than $(1 + \varepsilon)$. This answers a recent question by Nöbel and Steiner. It is the first known inapproximability result for the circuit diameter, and extends Sanità's inapproximability result of the diameter to the totally unimodular case.

翻译：多胞体的直径是一个基本几何参数，对理解单纯形法的效率至关重要。尽管其具有核心意义，计算给定多胞体直径的计算复杂性至今仍未得到充分理解。早在1994年，Frieze与Teng [Comp. Compl.] 就认识到该任务可能比NP难问题更为困难，并提出对应的判定问题是否属于多项式层级第二阶段的完备问题，即$Π^p_2$完备问题。在随后的研究中，部分结果得以获得。在奠基性工作中，Frieze与Teng证明了针对自定义多胞体族的弱NP难性。Sanità [FOCS18] 在突破性成果中证明，即使对于更简单的分数匹配多胞体，该问题也属于强NP难问题。最近，Steiner与Nöbel [SODA25] 将该结果推广至更简单的二分完美匹配多胞体与电路直径。本文最终证明：计算二分完美匹配多胞体的直径属于$Π^p_2$难问题。由于对应的判定问题显然包含于$Π^p_2$，这明确回答了Frieze与Teng提出的三十年悬疑问题。我们的结论在将直径替换为电路直径时依然成立。作为第二项主要成果，我们证明存在$\varepsilon > 0$，使得二分完美匹配多胞体的（电路）直径无法以优于$(1 + \varepsilon)$的近似比进行逼近。这回应了Nöbel与Steiner近期提出的问题。该结果是电路直径的首个不可逼近性证明，并将Sanità关于直径的不可逼近性结果扩展至全幺模情形。