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

这个项目涉及的研究类的结构， 在资源受限的并行计算模型中可计算的函数， 例如并行随机存取机和布尔族 电路. 该项目具体涉及（1）等式逻辑， 高级泛函，有限类型lambda演算和相关的 编程语言相关的并行复杂性类NC的 多对数时间及其子类和（2）布尔电路 复杂性，一个不变性群族之间的关系 语言及其平行复杂性， 正则语言的“代数”结构，以及 Bel'tyukov的低级统一并行复杂度类 堆栈寄存器机器。 这项研究将使用复杂性理论，证明 理论（数理逻辑）、组合学和有限群理论。 关于方程逻辑、lambda演算和更高类型的工作 泛函和Bel'tyukov机器将建立在新的递归上 并行复杂性类NC的理论刻画和 它的子类。 这项研究的目的是增加我们对 并行复杂性类：（1）高类型泛函导致 顺序，模块化编程语言，精确计算 某些并行复杂性类的函数，（2）自由变量 方程逻辑揭示了组合原理， 计数和承认多项式大小弗雷格证明，一个方向， 与N P =？co-NP问题，（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.