Structural Properties of Parallel Complexity Classes

点击翻译按钮获取中文摘要

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.