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

本课题研究资源有界并行计算模型中可计算函数类的结构，如并行随机存取机和布尔电路族。该项目特别关注(1)方程逻辑、高类型泛函、有限类型λ演算和与多对数时间并行复杂性类NC及其子类相关的相关编程语言；(2)布尔电路复杂性，语言的不变群族与其并行复杂性之间的关系；正则语言的“代数”结构与Bel'tyukov的堆栈寄存器机器的低级统一并行复杂性类的表征之间的关系。本研究将使用复杂性理论、证明理论（数理逻辑）、组合学和有限群论的技术。关于等式逻辑、λ演算和高级泛函以及别尔久科夫机的工作将建立在并行复杂类NC及其子类的新的递归理论表征上。这项研究的目的是增加我们对并行复杂性类的理解：(1)高级函数导致了顺序的、模块化的编程语言，这些语言精确地计算了某些并行复杂性类的函数；(2)自由变量方程逻辑揭示了涉及计数的组合原理，并承认多项式大小的Frege证明，这是与N P =？(3) Bel' yukov机将阐明低水平并行复杂度类的包含问题。

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.