Algebraic complexity theory via the algebraic geometry and representation theory of generalised continued fractions

通过代数几何和广义连分数表示论的代数复杂性理论

• 批准号: EP/W014882/2
• 负责人: Christian Ikenmeyer
• 金额: $ 37.03万
• 依托单位: University of Warwick
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2023
• 资助国家: 英国
• 起止时间: 2023 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FW014882%2F2
• 关键词: Algebraic; complexity; theory; via; algebraic

High-end computers can solve extremely difficult tasks, but even the best computers have limits in what they can do. These limits are studied in the field of computational complexity theory. The most famous question in computational complexity theory is the P vs NP conjecture, where a price of $1,000,000 will be awarded to the person or group who resolves it. The question can be phrased in terms of Boolean circuits and algorithms as follows. A Boolean circuit is a description of a finite sequence of logical operations that is performed a list of input values, much like a computer program, but with no loops. Given a Boolean circuit we want to know if there exists an input that makes it output TRUE. The P vs NP conjecture states that there is no efficient algorithm for this task. More precisely, the computation time required to answer this question for a circuit that is described using n symbols grows faster than any polynomial in n: Superpolynomially fast. This is independent of the algorithm that is used to answer the question. It is generally assumed among researchers that we are very far from resolving the P vs NP conjecture though. Instead of studying Boolean circuits many algorithmic breakthroughs are based on algebraic insights, for example the Euclidean algorithm, the effective Chinese Remainder Theorem, Gaussian elimination, Newton iteration, fast matrix multiplication, fast polynomial multiplication, fast Fourier transform, Elliptic Curve Cryptography, Reed-Solomon codes, or solving systems of polynomial equations via Gröbner bases. One more important example is Horner's method, a way of evaluating polynomials in a single variable efficiently. In 1966 Victor Pan proved that Horner's method is optimal if we count the number of arithmetic operations instead of Boolean operations. Using this way of measuring the complexity of a problem, in 1979 Leslie Valiant FSR defined algebraic analogues of the P vs NP problem. In this proposal we focus on Valiant's VF vs VNP conjecture. This conjecture says that the required size of arithmetic formulas counting the number of Hamiltonian cycles in directed graphs, a problem from combinatorics, grows superpolynomially. This is closely related to the P vs NP conjecture: If P equals NP, then the so-called polynomial hierarchy collapses, which most complexity theorists think does not happen. If one proves that this collapse does not happen, then this also implies that VF is not equal to VNP by a result of Karp and Lipton in 1980, so in a sense the VF vs VNP conjecture has to be resolved in order to make progress.We hope to make progress on the VF vs VNP conjecture, because a recent paper (Bringmann, Ikenmeyer, Zuiddam 2017) shows a deep connection between arithmetic formula size and a multivariate (i.e., several variables) version of Horner's method. This means that separating VF and VNP boils down to understanding the multivariate Horner's method on a deep level. It has connections to continued fractions and the continuant polynomial, which was recently studied by Charles Conley and Valentin Ovsienko (2018). Other than their work, only preliminary algebraic, geometric, and algorithmic results are known so far (very recently by Shpilka and Medini) and we aim to provide the missing foundations. We aim to connect our new insights in several ways with Geometric Complexity Theory, a mathematical approach for complexity lower bounds that uses algebraic geometry and representation theory and that was founded in 2001 by Ketan Mulmuley and Milind Sohoni. This will lead to new ways of proving lower bounds on arithmetic formula size, which then ultimately can help to separate VF and VNP.

高端计算机可以解决极其困难的任务，但即使是最好的计算机也有其能力的限制，这些限制是在计算复杂性理论领域中研究的。计算复杂性理论中最著名的问题是 P vs NP 猜想。其中解决该问题的个人或团体将获得 1,000,000 美元的奖励。该问题可以用布尔电路和算法来表述，如下所示。布尔电路是对有限逻辑运算序列的描述。执行一系列输入值，很像计算机程序，但没有循环，我们想知道是否存在使其输出 TRUE 的输入。 P 与 NP 猜想表明没有有效的算法。更准确地说，对于使用 n 个符号描述的电路，回答该问题所需的计算时间比 n 中的任何多项式增长得更快：这与用于回答该问题的算法无关。研究人员普遍认为不过，我们距离解决 P vs NP 猜想还很远，许多算法的突破不是基于布尔电路的研究，而是基于代数的见解，例如欧几里得算法、有效的中国剩余定理、高斯消元法、牛顿迭代、快速矩阵乘法，快速多项式乘法、快速傅里叶变换、椭圆曲线密码学、里德-所罗门码或通过 Gröbner 求解多项式方程组一个更重要的最佳例子是霍纳方法，一种有效评估单个变量多项式的方法。1966 年，维克多·潘证明了霍纳方法是用这种方法来计算算术运算的数量而不是布尔运算。问题的复杂性，1979 年 Leslie Valiant FSR 定义了 P 与 NP 问题的代数类似物。在这个提案中，我们重点关注 Valiant 的 VF 与 VNP 问题。该猜想表明，计算有向图中哈密顿循环数的算术公式所需的大小是超多项式增长的，这与 P 与 NP 猜想密切相关：如果 P 等于 NP，则称为多项式层次结构崩溃，大多数复杂性理论家认为这不会发生。如果证明这种崩溃没有发生，那么这也意味着 VF 不等于 VNP。 Karp 和 Lipton 在 1980 年提出，所以从某种意义上说，必须解决 VF vs VNP 猜想才能取得进展。我们希望在 VF vs VNP 猜想上取得进展，因为最近的一篇论文（Bringmann, Ikenmeyer, Zuiddam 2017）显示了算术公式大小和霍纳方法的多变量（即多个变量）版本之间的深层联系，这意味着分离 VF 和 VNP 会沸腾。深入理解多元霍纳方法与查尔斯·康利和瓦伦丁·奥夫辛科最近研究的连续分数和连续多项式（2018）除了他们的工作之外，只有初步的代数、几何和算法。到目前为止，我们已经知道了结果（Shpilka 和 Medini 最近），我们的目标是提供缺失的基础。我们的目标是通过多种方式将我们的新见解与几何复杂性理论（一种数学）联系起来。使用代数几何和表示理论的复杂性下界方法，由 Ketan Mulmuley 和 Milind Sohoni 于 2001 年创立，这将带来证明算术公式大小下界的新方法，最终有助于分离 VF 和 VNP。 。