易于计算序列的猜想：证明与计算复杂性的关联

本文主要探讨了计算复杂度理论中的一个重要概念——易于计算的序列，并提出了一个猜想，即某些特定的序列（如[2nln2]或n!）可能不容易被计算。作者Pascal Koiran在此研究中证明了这个猜想对于特定序列的证实将对计算复杂度理论产生深远影响，例如揭示超多项式下界的算术电路大小或证明永久问题与P/≠PSPACE的关系。 计算复杂度是计算机科学中的核心理论领域，关注的是算法执行时间和资源消耗的问题。τ(n)函数定义为从常数1和2通过加、减、乘运算构造整数n所需的最小运算次数，用于衡量数值计算的复杂度。一个序列xn被称为“易于计算”如果存在一个多项式p，使得对于所有n，τ(xn)的增长不超过p(log n)。如果不存在这样的多项式，序列则被认为是“难以计算”。 文章中提到的猜想是，例如序列[2nln2]和阶乘序列n!可能是难以计算的。Shub和Smale已证明，如果n!确实难以计算，那么在复数域上P=NP问题的解决将成为可能，这是一个著名的未解决问题。然而，至今为止，n!是否难以计算仍然是开放问题。 此外，文章讨论了DeMelo和Svaiter的工作，他们指出对于大多数整数，τ(n)的下界至少是(log n)/(log log n)，这暗示大部分整数具有较高的计算复杂度。然而，找到特定序列的精确下界是一项挑战，这类似于计算复杂度理论中证明问题难度的难题。 Koiran在这篇文章中提出，证明某些序列的τ复杂度下界可能是困难的，因为这可能会揭示出计算复杂度理论中的新边界，比如超多项式下界的算术电路大小。对于序列[2nln2]，其难以计算的证明将意味着永久多项式的计算复杂度有超多项式下界。而对于序列n!，如果证明其难以计算，那么将暗示永久问题不在P类中，即P≠PSPACE。 关键词涉及了Valiant的研究，以及计算复杂度的分类68Q15（计算复杂性理论）、68Q17（算法的复杂性）和03D15（计算理论的模型和复杂性）。这篇文章深入探讨了计算复杂度理论中的一个关键问题，即如何判断和证明序列的计算复杂性，并展示了这一研究对理论计算科学的潜在贡献。