Arithmetic versus Boolean Complexity: The Case of Small-Depth Circuits

计算复杂度的范围由寻找有效算法（上界）和证明某种复杂度的算法不存在（下界）决定。近年来，算术电路已经成为一种非常流行的计算模型，因为算法（特别是从数值分析等领域）可以非常自然地制定在这个模型中，但也因为其非常有限的（"结构化“）的自然界有许多令人印象深刻的下限是已知的。在上一个世纪的八十年代和九十年代，布尔电路被广泛研究，因为发明了获得下界的深层技术。这将是该项目的目的，利用算术和布尔电路之间的连接，以一种比目前更系统的方式，攻击这两个领域中一些最重要的开放问题。期望的结果将有望扩大我们的理解的结构内的所有有效解决问题的类P的小复杂类。

The area of computational complexity is determined by the search for efficient algorithms (upper bounds) as well as for proofs that algorithms of certain complexity do not exist (lower bounds). Arithmetic circuits have turned into a very popular computation model in the recent past, because algorithms (in particular from areas such as numerical analysis) can be very naturally formulated in this model, but also because of its very restricted (``structured'') nature a number of impressive lower bounds are known.In the eighties and nineties of the previous century, Boolean circuits were widely studied because of the invention of deep techniques for obtaining lower bounds. It will be the aim of this project to exploit connections between arithmetic and Boolean circuits in a more systematic way than up to date, to attack some of the most important open questions in both areas. The desired results will hopefully broaden our understanding of the structure of small complexity classes within the class P of all efficiently solvable problems.