Low-Level Complexity and 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.