Computational Complexity Theory and Circuit Complexity

本研究将研究计算的复杂性， 布尔电路复杂性的框架。 特别强调 关于以下专题： 电路类的强分离：如果已知小的 电路复杂性类可以加强，这将意味着 分离更大的时间和空间复杂性类。 这 将使用“豁免权”的概念， 工具. 宽度有界约简：这个概念将被用作一个工具， 研究“相似”复杂性类之间的关系。 本项目还研究了阈值电路， 复杂度类P/poly

This research will study the complexity of computation using the framework of Boolean circuit complexity. Special emphasis is placed on the following topics: Strong separations of circuit classes: If known separations of small circuit complexity classes could be strengthened, it would imply separations on larger time- and space-complexity classes. This connection will be investigated, using the notion of "immunity" as a tool. Width-bounded reducibility: This notion will be used as a tool to investigate the relationships among "similar" complexity classes. This project also investigates threshold circuits, an structure of the complexity class P/poly.