"Parallel Computation and Boolean Circuits - lambda calculus, equational theories, modular counting and permutation groups"

本项目主要研究资源受限并行计算模型中可计算函数类的结构，如并行随机存取机和布尔电路族。该项目具体涉及(1)与多对数时间的并行复杂性类NC及其子类有关的方程逻辑、高阶泛函、有限类型Lambda演算和相关的程序设计语言，以及(2)布尔电路复杂性，语言的不变群族与其并行复杂性之间的关系，正则语言的“代数”结构之间的关系，以及用Bel‘tyukov的堆栈寄存器机器刻画低级一致并行复杂性类。这项研究将使用复杂性理论、证明论(数理逻辑)、组合学和有限群论的技术。关于方程逻辑、Lambda演算和高型泛函以及Bel‘tyukov机器的工作将建立在并行复杂性类NC及其子类的新的递归理论特征的基础上。这项研究的目的是增加我们对并行复杂类的理解：(1)更高类型的泛函导致了顺序的、模块化的程序设计语言，它准确地计算了某些并行复杂类的函数；(2)自由变量方程逻辑阐明了涉及计数的组合原理，并允许多项式大小的Frege证明，这是与N-P=？CO-N P问题，(3)Bel‘tyukov机器将澄清低级别并行复杂性类的包容问题。

This project concerns the study of the structure of classes of functions computable in resource bounded parallel computation models, such as the parallel random access machine and families of boolean circuits. The project specifically concerns (1) equational logics, higher-type functionals, finite typed lambda calculi and associated programming languages related to the parallel complexity class NC of polylogarithmic time and its subclasses and (2) boolean circuit complexity, the relation between the family of invariance groups of a language and the its parallel complexity, the relation between the "algebraic" structure of a regular language, and characterization of low-level uniform parallel complexity classes in terms of Bel'tyukov's stack-register machines. This research will use techniques from complexity theory, proof theory (mathematical logic), combinatorics, and finite group theory. The work on equational logics, lambda calculi and higher-type functionals, and Bel'tyukov machines will build on new recursion theoretic characterizations of the parallel complexity class NC and its subclasses. The goal of this research is to increase our understanding of parallel complexity classes: (1) higher type functionals lead to sequential, modular programming languages which compute exactly the functions of certain parallel complexity classes, (2) free variable equational logics shed light on combinatorial principles involving counting and which admit polynomial size Frege proofs, a direction of research related to the N P =? co- N P question, (3) Bel'tyukov machines will clarify questions of containment of low level parallel complexity classes.