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类。因此，P与NP问题的肯定答案将具有巨大的算法含义。这也意味着一种方法来打破任何公钥密码系统，因为这种系统的安全性取决于假设NP中的特定问题不属于P.这个研究项目的目的是开发技术来确定复杂性类之间的关系，如P和NP：分离和包含。在分离方面，研究人员专注于不受相对化和自然证明的已知陷阱影响的技术。特别是，他们专注于间接对角化和展示完整问题的独特属性。在包容性方面，重点是时间和空间有限的概率和量子计算的有效经典模拟，教育目标包括伪随机性和去随机化以及量子计算的研究生课程的发展。在本科阶段，研究人员计划进一步整合核心课程中的离散结构。