博文

[转载] 一个"未解決的計算機科學問題"的导出

已有 2374 次阅读 2019-10-13 15:32 |系统分类:科普集锦|文章来源:转载

周末娱乐一下, 科普一点小知识。"Is there an algorithm that can find a simple closed quasigeodesic on a convex polyhedron in polynomial time?" 是一个未解決的計算機科學問題。它是如何导出的呢？See

https://en.wikipedia.org/wiki/Theorem_of_the_three_geodesics (Theorem_of_the_three_geodesics.pdf) (谷歌自动翻译):

在微分几何中，三个测地线的定理表明，每个球面拓扑的黎曼流形具有至少三个闭合测地线，它们形成了没有自相交的简单闭合曲线。结果还可以扩展到凸多面体上的准测地学。

这一结果源于海洋航行的数学原理，其中可以通过椭球准确地对地球表面进行建模，还得益于对椭球上的测地线的研究，这是船舶航行的最短路径。特别是，近球形的三轴椭球体只有三个简单的闭合测地线，即赤道。

-- 1905年，亨利·庞加莱（HenriPoincaré）猜想，每个在拓扑上等效于球体的光滑表面同样包含至少三个简单的封闭测地线，并在

-- 1929年拉扎尔·柳斯特尼克（ Lazar Lyusternik）和列夫 ·史尼尔勒曼（ Lev Schnirelmann）发表了这一猜想的证明，后来发现了这一猜想有缺陷。该证明由汉斯·沃纳·巴尔曼（ Hans Werner Ballmann）在

-- 1978年修复。

该猜想的一个证明是检验球体上平滑曲线空间的均一性，并使用曲线缩短流来找到一个简单的闭合测地线，该测地线代表该空间的三个非平凡的同质性类别中的每一个。

更重要的是，必须存在三个简单的闭合测地线，它们的长度最多与表面的直径成比例。

在光滑的拓扑球上，长度最大为L的闭合测地线的数量与L / log L成正比，但并非所有此类测地线都能保证简单。

在紧致的双曲 Riemann曲面上，有无限多个简单的闭合测地线，但在给定的长度范围内只有有限的多个。它们通过Selberg zeta函数进行解析编码。 Maryam Mirzakhani研究了简单闭合测地线数量的增长率（取决于长度）。

非平滑指标

还可以在并非到处都是光滑的某些表面上定义测地线，例如凸多面体。尽管某些多面体具有简单的封闭测地线（例如，规则四面体和双曲面具有无限多的封闭测地线，全都是简单的）其他则没有。特别是，凸多面体的简单闭合测地线必须将顶点的总角缺陷一分为二，并且几乎所有多面体都不具有这样的二等分线。

不过，可以通过考虑准测地线将这三个测地线的定理扩展到凸多面体，即除多面体的顶点处的测地线以外的曲线，并且在它们相交的每个顶点的两侧角度均小于π 。凸多面体的三个测地线定理的一个版本表明，所有多面体都至少具有三个简单的封闭准测地学。这可以通过用光滑表面逼近多面体并将三个测地线定理应用于该表面来证明。是否可以在多项式时间内构造这些准测地学是一个悬而未决的问题。

References:

未解決的計算機科學問題: (List_of_unsolved_problems_in_computer_science.pdf)