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.