Low-Level Complexity and Hard Concepts

低级复杂性和硬概念

• 批准号: 9821040
• 负责人: Kenneth Regan
• 金额: $ 17.85万
• 依托单位: SUNY at Buffalo
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-09-15 至 2002-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9821040&HistoricalAwards=false
• 关键词: Low; Level; Complexity; Hard; Concepts

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.

本计画将计算复杂性理论中的“多项式方法”延伸至多项式思想与代数几何。 吸引人的是，后者的概念是很难足以克服“自然证明”的障碍，以取得进展的下限，但仍然是一个自然的和重要的身体数学的一部分。 多项式思想的Grobner理论表明，其中永久函数比行列式更复杂，并将其与类似于Hastad的限制方法的思想相结合，表明有希望将永久函数的复杂性类#P从NC层次中分离出来。 该项目还旨在量化电路类中非均匀性的计算意义，从PI获得的自然计算问题的电路上收紧“尺寸扩展权衡”，确定“自然证明”框架是否将irom多项式扩展到准线性tine，并扩展Forthnow在准线性尺寸电路类上的工作。 这项工作的目的是增加科学知识的内在成本的计算问题，这是很重要的研究人员在许多领域。