CAREER: Techniques for Separations and Inclusions of Complexity Classes

计算复杂性是对计算问题固有难度的研究。该理论考虑了各种计算模型，如经典计算机、概率计算机和量子计算机。对于其中的每一个，它的目的是描述计算问题的解决方案需要多少资源作为问题大小的函数。复杂性理论中最突出的开放问题是，有效验证候选解的有效性的能力是否意味着有效计算有效解（假设存在有效解）的能力。这个问题通常是根据相应的计算问题类别来陈述的：NP是否包含在P中？几乎任何学科的许多计算问题都属于NP类，但不属于P类。因此，P与NP问题的正面答案将具有巨大的算法含义。它也意味着一种破解任何公钥加密系统的方法，因为这种系统的安全性依赖于NP中的特定问题不属于P的假设。该研究项目旨在开发确定复杂类（如P和NP）之间关系的技术：分离和包含。在分离方面，研究人员将重点放在那些不会遭受已知的相对论和自然证明陷阱的技术上。特别地，他们集中于间接对角化和展示完全问题的区别性质。在包含方面，重点在于时间和空间有界概率和量子计算的有效经典模拟。教育目标包括发展伪随机和非随机化以及量子计算的研究生课程。在本科阶段，研究人员计划在核心课程中进一步整合离散结构。

Computational complexity is the study of the inherent difficulty ofcomputational problems. The theory considers various models of computation, such as classical computers, probabilistic computers, and quantum computers. For each of these, it aims to describe how many resources are needed to compute the solution to a problem as a functionof the problem size.The most prominent open question in complexity theory is whether theability to efficiently verify the validity of a candidate solution implies the ability to efficiently compute a valid solution (assumingone exists). The question is usually stated in terms of the corresponding classes of computational problems: Is NP contained in P? Lots of computational problems from virtually any discipline fall inthe class NP but are not known to be in P. Therefore, a positive answer to the P versus NP question would have tremendous algorithmic implications. It would also imply a way to break any public-key cryptographic system, as the security of such systems rests on the assumption that a particular problem in NP does not belong to P.This research project aims to develop techniques for determining the relationships between complexity classes like P and NP: separations and inclusions. On the separation side, the investigators focus on techniques that do not suffer from the known pitfalls of relativization and natural proofs. In particular, they concentrate on indirect diagonalization and exhibiting distinguishing properties of complete problems. On the inclusion side, the emphasis lies on efficient classical simulations of time and space bounded probabilistic and quantum computations.The educational goal consists of the development of graduate courses on pseudo-randomness and derandomization and on quantum computing. At the undergraduate level, the investigators plan to further the integration of discrete structures in the core curriculum.