Structural Properties of Parallel Complexity Classes

本项目旨在通过比较在并行计算模型上定义的复杂度类和在顺序模型上定义的复杂度类来研究并行计算的能力。作为一个并行模型，我们使用运行速度非常快的逻辑电路，可以有边界或无界扇入。它们分别产生NC类和AC类。相对化方法和分解技术都用于查看这些类的结构，并将它们与顺序类（如L、NL和p）进行比较。该项目还将研究空间有界的不确定性层次结构。

This project is intended to study the power of parallel computation by comparing complexity classes defined on parallel models of computation with those defined on sequential models. As a parallel model, we use logical circuits that operate very quickly and that may have either bounded or unbounded fan-in. These yield the classes NC and AC, respectively. Relativized methods and a decomposition technique are both used to look at the structure of these classes and to compare them to sequential classes such as L, NL and P. This project will also investigate the structure of space bounded nondeterministic hierarches.