标题： 曲面同胚的均匀多项式时间分类 显示英文标题

标题： Uniformly polynomial-time classification of surface homeomorphisms

摘要： 我们描述了一个算法，该算法给定曲面$S$上的两个本质曲线，可以计算它们在$S$的曲线图中的距离，最多有乘法和加法误差。 作为应用，我们提出了一个算法来判断映射类$S$的 Nielsen-Thurston 类型（周期性、可约或伪Anosov）。 我们算法的新颖之处在于，其运行时间与输入大小和$S$的复杂度（例如，其欧拉示性数）呈多项式关系。 这与之前已知的算法形成对比，这些算法对于任何固定的曲面$S$，其运行时间仅与输入大小呈多项式关系。 显示英文摘要

摘要： We describe an algorithm which, given two essential curves on a surface $S$, computes their distance in the curve graph of $S$, up to multiplicative and additive errors. As an application, we present an algorithm to decide the Nielsen-Thurston type (periodic, reducible, or pseudo-Anosov) of a mapping class of $S$. The novelty of our algorithms lies in the fact that their running time is polynomial in the size of the input and in the complexity of $S$ -- say, its Euler characteristic. This is in contrast with previously known algorithms, which run in polynomial time in the size of the input for any fixed surface $S$.