Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture
Peter Bürgisser, Mahmut Levent Doğan, Visu Makam, Michael Walter and Avi Wigderson
当一个群体在一个布景上行动时,它自然地将其分割成轨道,从而产生轨道问题。 这些是自然的算法问题,因为对称性在物理学,数学,计算机科学,优化等众多问题和结构中都是核心。 因此,了解其计算复杂性是高度感兴趣的。 最近,Bürgisser等人给出了第一个关于轨道问题的多项式时间算法,即欧几里得空间上的交换连续组的行动。 在这项工作中,在理论和实际应用的激励下,我们研究了这些轨道问题的稳健泛化的计算复杂性,这相当于将C^n的轨道距离近似到一个因素 γ>1。 特别是,这允许决定两个输入是否大约在同一轨道上或远非如此。 一方面,我们通过减少离它最近的向量问题,证明 γ = n^Ω(1/loglog n) 此问题的 NP 硬度。 另一方面,我们描述了为近似因子 γ = exp(poly(n))解决这个问题的算法。 我们的算法结合了不变理论和算法格子理论的工具,它们也提供了见证给定轨道接近的群元素(与先前工作的代数算法相反)。 我们证明,只有当著名的数字理论abc猜想的版本成立时,它们才会在多项式时间运行 - 在计算复杂性和数论之间建立一种新的令人惊讶的联系。
When a group acts on a set, it naturally partitions it into orbits, giving rise to orbit problems. These are natural algorithmic problems, as symmetries are central in numerous questions and structures in physics, mathematics, computer science, optimization, and more. Accordingly, it is of high interest to understand their computational complexity. Recently, Bürgisser et al. gave the first polynomial-time algorithms for orbit problems of torus actions, that is, actions of commutative continuous ...
