PYI: Structural Complexity Theory

可行计算的结构将决定我们能否有效地解决自然和现代世界提出的优化问题。该项目调查哪些问题有有效的解决方案，以及为什么一些问题缺乏计算上可行的算法。特别感兴趣的是复杂性类之间的结构关系，以及复杂性类的内部结构。一个长期目标是表明，计算复杂性的“结构”方法是一种广泛适用的研究范式，是算法的伴侣。许多领域的结构方法(包括实值计算和零知识理论)将被追求，结构复杂性理论的许多主题(包括低、正约简、排序和同构猜想)将被重新审查。

The structure of feasible computations will determine whether we can efficiently solve the optimization problems posed by nature and the modern world. The project investigates which problems have efficient solutions, and why some problems lack computationally feasible algorithms. Of particular interest are the structural relationships between complexity classes, and the internal structure of complexity classes. A long-term goal is to show that the "structural" approach to computational complexity is a broadly applicable paradigm of research, and a companion to algorithms. Structural approaches to many areas (including real-valued computation and zero-knowledge theory) will be pursued, and many themes of structural complexity theory (including lowness, positive reductions, ranking, and the isomorphism conjecture) will be re-examined.