CAREER: Techniques for Separations and Inclusions of Complexity Classes

职业：复杂类的分离和包含技术

• 批准号: 0133693
• 负责人: Dieter van Melkebeek
• 金额: $ 32.9万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0133693&HistoricalAwards=false
• 关键词: CAREER; Techniques; Separations; Inclusions; Complexity

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.

计算复杂性是对计算问题的固有难度的研究。该理论考虑了各种计算模型，例如古典计算机，概率计算机和量子计算机。对于这些中的每一个，它旨在描述需要多少资源来计算问题的解决方案作为问题大小的函数。这个问题通常以相应的计算问题类别来指定：NP是否包含在P中？几乎所有学科的计算问题都属于NP类，但尚不知道。因此，对P与NP问题的积极答案将具有巨大的算法含义。这也意味着打破任何公开密码系统的一种方法，因为此类系统的安全性基于以下假设：NP中的特定问题不属于P.该研究项目旨在开发用于确定P和NP等复杂性类别之间关系的技术：分离和包容性。在分离方面，研究人员专注于没有遭受相对化和自然证明陷阱的技术。特别是，它们集中在间接对角线上，并表现出完全问题的区分特性。在包容性方面，重点在于对时间和空间有限的概率和量子计算的有效经典模拟。教育目标包括开发有关伪随机性和衍生物以及量子计算的研究生课程。在本科生，研究人员计划进一步整合核心课程中的离散结构。