PYI: Structural Complexity

该项目旨在了解计算资源和计算资源层次结构之间的权衡。特别令人感兴趣的是可行的(多项式时间)计算、NP完备性以及时间和空间以及决定论和非决定论之间的关系。例如，这项研究解决了这个问题提出的微妙之处，“在什么情况下，$k+1$位的信息在计算上比只有$k$位的信息更有用？”目前还在研究具有实际意义的问题，如使用专用硬件进行排序、并行模型中的故障检测、处理器和互连网络的有效布局以及DNA测序。

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.