PYI: Structural Complexity

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

This project is aimed at understanding the tradeoffs among computational resources and hierarchies of computational resources. Of particular interest are feasible (polynomial-time) computation, NP- completeness, and the relationships between time and space and between determinism and nondeterminism. For example, the research addresses subtleties raised by the question, "When are $k+1$ bits of information more computationally useful than only $k$ bits of information?" Also under investigation are issues of current practical importance, such as sorting with special-purpose hardware, fault detection in parallel models, efficient layouts of processor and interconnection networks, and DNA sequencing.