Computational Complexity Theory and Circuit Complexity

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

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.