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

点击翻译按钮获取中文摘要

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.