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.