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.

高端计算机可以解决极其困难的任务，但是即使是最好的计算机也有限制他们可以做的事情。这些限制在计算复杂性理论领域进行了研究。计算复杂性理论中最著名的问题是PS与NP的猜想，其中将授予解决方案的人或团体的价格为1,000,000美元。可以根据布尔电路和算法来措辞，如下所示。布尔电路是对逻辑操作有限顺序的描述，该逻辑操作执行了输入值列表，就像计算机程序一样，但没有循环。给定一个布尔电路，我们想知道是否存在使其输出成真的输入。 P VS NP猜想指出，此任务没有有效的算法。更确切地说，为使用n个符号描述的电路回答此问题所需的计算时间比N：superpolynomems中的任何多项式都快。这与用于回答问题的算法无关。在研究人员中，通常认为我们还没有解决PS NP的猜想很远。 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通过Gröbner基地。一个更重要的例子是霍纳的方法，一种有效评估单个变量中多项式的方法。 1966年，维克多·潘（Victor Pan）证明，如果我们计算算术操作的数量而不是布尔操作，那么霍纳的方法是最佳的。使用这种衡量问题的复杂性的方式，1979年，莱斯利·瓦利安（Leslie Valiant FSR）定义了P与NP问题的代数类似物。在此提案中，我们关注Valiant的VF与VNP协议。这个猜想说，算术公式的所需大小计算了有向图中的哈密顿周期的数量，这是一个来自组合物的问题，在超级杂质上生长。这与p vs np一致性密切相关：如果p等于np，则所谓的多项式层次结构崩溃，理论家认为这不是发生的大多数复杂性。如果一个人证明没有发生这种崩溃，那么这也意味着1980年KARP和LIPTON的结果，VF不等于VNP，因此从某种意义上说，VF VS VS VNP猜想必须得到解决，以取得进展才能取得进展。算术公式的大小和霍纳方法的多元变量（即几个变量）。这意味着将VF和VNP锅炉分开，以深入了解多元霍纳的方法。它与持续的分数和持续多项式有联系，这是Charles Conley和Valentin Ovsienko（2018）最近研究的。除了他们的工作外，迄今为止（最近由Shpilka和Medini迄今为止，只知道了初步代数，几何和算法结果），我们的目标是提供缺失的基础。我们旨在通过几种方式将新见解与几何复杂性理论联系起来，这是一种使用代数几何学和表示理论的复杂性降低界限的数学方法，并且由Ketan Mulmuley和Milind Sohoni于2001年建立。这将导致在算术公式大小上证明下限的新方法，然后最终可以帮助分离VF和VNP。