Low-Level Complexity and Hard Concepts

本项目扩展了计算复杂性理论中的“多项式方法”，涉及多项式思想和代数几何。吸引人的地方在于，后一种概念很难克服“自然证明”的障碍，从而在下界上取得进展，但仍然是自然而重要的数学主体的一部分。格罗布纳多项式思想理论表明，永久函数比行列式更复杂，并将其与类似于哈斯达的限制方法的思想结合起来，表明有希望将永久函数的复杂性类#P从NC层次中分离出来。该项目还旨在量化电路类非均匀性的计算意义，这源于PI对自然计算问题的电路的“尺寸-扩展权衡”的收紧，确定“自然证明”框架是否从多项式时间延续到拟线性时间，以及对Forthnow在拟线性尺寸电路类上的工作的扩展。这项工作的目的是增加关于计算问题内在成本的科学知识，这对许多领域的研究人员都很重要。

This project extends the "Polynomial Method" in computational complexity theory to involve polynomial ideas and algebraic geometry. The attraction is that the latter concepts are hard enough to surmount the "Natural Proofs" obstacle to progress on lower bounds, yet are still part of a natural and important body mathematics. The Grobner theory of polynomial ideas shows regard in which the permanent function is more complex than the determinant, and combining it with an idea analogous to Hastad's method of restrictions shows promise of separating the permanent's complexity class #P from the NC hierarchy. The project also aims to quantify the computational significance of non-uniformity in circuit classes, growing out from the tightening the "Size-expansion tradeoffs" on circuits for natural computational problems obtained by the PI, determining whether the "Natural Proofs" framework carries over irom polynomial to quasilinear tine, and extending work by Forthnow on quasi-linear size circuit classes. The objective of this work is to increase scientific knowledge about the intrinsic cost of computational problems, which is important to researchers in many fields.