"Algebraic and logical approaches to circuit complexity"

该项目考察了由各种描述的无界扇入门构建的恒定深度电路族可解决的问题类的结构。所考虑的所有类都包含在复杂度类NC1中，这是一个用非常快的并行算法求解的问题族模型。研究的主要目标是回答一些关于这些类别中包含的开放性问题；特别是，为了解决对于NC1而言，对于定深约简，迭代加法对m取模还是多数问题是完全的问题。这项工作将采用最近发现的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.