Computational Complexity Theory and Circuit Complexity

复杂性理论研究的目标是通过提供解决这些问题所需资源的下界来对现实世界计算问题的复杂性进行分类。迄今为止，尽管对于受限类型的电路有令人印象深刻的下界，但实现这一目标的唯一有用的进展几乎是通过可约性的工具，它允许人们表明问题对于复杂类是完整的。许多最重要的复杂性类都可以用布尔电路来表征，布尔电路的大小或深度都受到限制，等等。最近，很明显算术电路在这方面也很有用。尽管最近在这方面取得了重大进展，但布尔和算术电路复杂性之间的关系仍然知之甚少。本项目将进一步澄清这些关系。特别地，这个项目将探索关于算术运算复杂性的新见解，以研究小空间有限的复杂度类和小深度电路中定义的复杂度类的能力。此外，为了更好地理解图可达性问题的复杂性，将应用Kolmogorov复杂度工具。更一般地说，该项目将试图澄清复杂性类之间的关系，以及定义描述重要复杂性类的计算模型的各种概念（不确定性、不模糊性、对称性、布尔和算术电路等）。

The goal of research in complexity theory is to classify the complexity of real world computational problems by providing lower bounds on the resources required to solve them. To date - in spite of impressive lower bounds for restricted types of circuits- almost the only useful progress toward this goal has come via the tool of reducibility, which allows one to show that problem is complete for complexity class.Many of the most important complexity classes can be characterized in terms of Boolean circuits of restricted size or depth, etc. Recently, it has become apparent that arithmetic circuits are also very useful in this regard. The relationships between Boolean and arithmetic circuit complexity are still only poorly understood, although there has been significant progress on this front recently. This project will work to clarify these relationships further.Specially, this project will exploit new insights about the complexity of arithmetic operation, in order to investigate the power of small space-bounded complexity classes and complexity classes defined in terms of small-depth circuits. Also the tools of Kolmogorov complexity will be applied, in order to obtain a better understanding of the complexity of graph reachability problems. More generally, the project will attempt to clarify the relationship among complexity classes, and the various notions (nondeterminism, unambiguity, symmetry, Boolean and arithmetic circuits, etc.) that define models of computation characterizing important complexity classes.