"Algebraic and logical approaches to circuit complexity"

该项目研究了由各种描述的无界扇入门产生的恒定深度电路族可解决的一类问题的结构。所有正在考虑的类都包含在复杂性类Nc1中，这是一类可通过非常快速的并行算法解决的问题的模型。这项研究的主要目的是回答一些关于这些类之间的包含的开放问题，特别是解决关于恒定深度约简的Nc1的迭代加法模或多数问题是否是完全的问题。这项工作将利用最近发现的NC1及其子类的形式逻辑和有限自动机的刻画。这些特征使得将模型论和代数方法应用于电路复杂性的研究成为可能。人们希望，除了解决这些迫在眉睫的问题外，还将产生一种新的方法来证明计算复杂性的下界，并希望这将有助于研究更高复杂性的类。

The project examines the structure of classes of problems solvable by constant-depth families of circuits biult from unbounded fan-in gates of various descriptions. All of the classes under consideration are contained in the complexity class NC1, which is a model for the family of problems solvable by very fast parallel algorithms. The principal goal of the research is to answer a number of open questions concerning the inclusions among these classes; in particular, to settle the question of wheather either iterated addition mod m or the majority problem is complete for NC1 with respect to constant-depth reductions. This work will employ the recently discovered characterization of NC1 and its subclasses in terms of formal logic and finite automata. These characterizations make it possible to apply model-theoretic and algebraic methods to the study of circuit complexity. It is hoped that, in addition to settling these immediate questions, a new methodology for proving lower bounds in computational complexity will result, and that this will be of benefit in studying classes of higher complexity.