Collaborative Research: AF: Small: Combinatorial Complexity Problems

计算复杂性是指需要什么样的计算资源，如时间、精力、空间和能量，来解决来自现实活动的具有挑战性的数学问题，例如设计飞机、分析DNA证据或破解密码。这个项目应用了组合学和代数的最新前沿工作，以更清楚地确定哪些问题是棘手的(在浪费太多计算资源试图解决它们之前)。这一点很重要，因为知道一个问题很难通过计算解决，可以用在不同的方向上，比如创建更难破解的代码。组合学是计算复杂数学对象的古老艺术，是早期数字计算机发展的摇篮。这里的代数指的是对某些对称的研究，这些对称最近被发现在复杂性理论中很重要。从技术上讲，这个项目从代数组合学的角度探讨几何复杂性理论，以进一步阐明VP与VNP问题的可行方法。具体地说，部分工作将分别致力于计算某些Young表的计数以及计算代数组合学和代数复杂性中的相关常数和多项式的计算复杂性。这些物体和数量虽然在上个世纪初被提出，但至今仍未被深入了解。然而，他们最近从各个方向享受到了健康的进步。了解它们的计算性质将澄清代数组合学中一些著名问题寻找自然对应(双射)的可行性，并为它们的研究铺平一条新的途径，导致代数复杂性的更好下界。这些对象和量包括理解Kronecker系数(一个80年前的问题)，以及有效地计算Kostka和Littlewood-Richardson系数。虽然这些系数没有封闭形式的公式，但它们的渐近性可能导致几何复杂性理论中目前无法企及的新下限。具体地说，区分像VP和VNP这样的算术复杂性类别归根结底是在仿射变换下区分它们的通用多项式(例如行列式和永久多项式)，最终转化为涉及所述量的表示理论多样性之间的不平等。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Computational complexity characterizes what kinds of computational resources,such as time, effort, space and energy, are needed to solve challenging mathematical problems derived from real-worldactivities, such as designingaircraft, analyzing DNA evidence, or breaking a secret code.This project applies recent cutting-edge work from combinatorics andalgebra to more clearly determine which problems are intractable (beforetoo many computational resources are wasted trying to solve them). This is important because,knowing that a problem is hard to solve computationally can beused in a different direction, such as creating codes that are harder tobreak. Combinatorics is the ancient art of counting complicated mathematicalobjects, and was the cradle for the development of early digital computers.Algebra here refers to the study of certain symmetries which have recentlybeen discovered to be important in complexity theory. More technically, this project approaches Geometric Complexity Theoryfrom the point of view of algebraic combinatorics to further clarifyfeasible approaches to the VP vs. VNP Problem.Specifically, part of the work will be devoted to the computational complexityof counting certain Young tableaux and computing related constantsand polynomials in Algebraic Combinatorics and Algebraic Complexity,respectively. These objects and quantities, while introduced in the beginningof last century, are still not deeply understood. However, they have recentlyenjoyed a healthy stream of advances fromvarious directions. Understanding their computational nature would clarify thefeasibility of some famous problems in Algebraic Combinatorics searching fornatural correspondences (bijections), and pave a new approach to their study,leading towards better lower bounds in algebraic complexity. These objects andquantities include understanding the Kronecker coefficients (an 80-year-oldproblem), and efficiently computing Kostka and Littlewood-Richardsoncoefficients. While no closed-form formulas for these coefficients exist,their asymptotics can lead to new lower bounds in Geometric Complexity Theorythat are currently out of reach.Specifically, distinguishing ArithmeticComplexity classes like VP and VNP boils down to distinguishing theiruniversal polynomials (e.g. determinant vs permanent) under affinetransformations, ultimately translating to inequalities between representationtheoretic multiplicities involving the quantities mentioned.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.