Computational Complexity Theory and Circuit Complexity

复杂性理论研究的最终目标是通过提供解决问题所需资源的下限来对现实世界计算问题的复杂性进行分类。到目前为止，尽管受限类型的电路有令人印象深刻的下界，但实现这一目标的几乎唯一有用的进展是通过简约性工具，它允许表明一个复杂类别的问题是完整的。因此，复杂性类成为复杂性理论的基本研究对象，复杂性类之间的关系是复杂性理论研究的基本问题。在弄清这些关系之前，计算中的许多重要活动(特别是公钥密码学)将依赖于不确定的猜想。许多最重要的复杂性类可以用有限大小或深度的布尔电路等来表征。最近，很明显，算术电路在这方面也非常有用。尽管最近在这方面取得了重大进展，但人们对布尔和算术电路复杂性之间的关系仍然知之甚少。这个项目将致力于进一步澄清这些关系，并将寻求利用算术复杂性类的代数特征来设计新的方法来证明下界。我们所知道的关于现实世界问题的复杂性的大部分来自于一个令人惊讶的事实，即绝大多数这样的问题对于经过充分研究的复杂类来说是完整的，在非常有限的约简下。最近的进展表明，在非常简单的同构下，这些集合实际上是彼此同构的。到目前为止，关于同构的工作主要是理论上的兴趣。这个项目将致力于看看同构定理是否可以用来获得关于现实世界问题的复杂性的实用信息。更广泛地说，这个项目将试图澄清复杂类之间的关系，以及各种概念(非确定性、无二义性、对称性、布尔和算术电路等)。它定义了表征重要复杂性类别的计算模型。

The final 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 to show that a problem is complete for a complexity class. Thus the complexity class has become the fundamental object of study in complexity theory, and the basic questions in the field concern the relationships among complexity classes. Until these relationships are clarified, many important activities in computing ( in particular: public-key cryptography) will rest on uncertain conjectures. 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 Booleau and arithmetric 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, and will seek to exploit the algebraic characteristics of arithmetic complexity classes to devise new approaches to prove lower bounds. Most of what we know about the complexity of real-world problems comes from the surprising fact that the overwhelming majority of such problems are complete for well-studied complexity classes, under very restrictive reducibilities. Recent progress has shown that these sets are actually isomorphic to each other, under very simple isomorphisms. Up to now, the work on isomorphisms has been primarily of theoretical interest. This project will work to see if the isomorphism theorems can be used to derive practical information about the complexity of real-world problems. More generally, this project will attempt to clarify the rel ationships among complexity classes, and the various notions (nondeterminism, unambiguity, symmetry, Boolean and arithmetic circuits, etc.) that define models of computation characterizing important complexity classes.