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 等类别：分离和包含。在分离方面，研究人员专注于不受相对化和自然证明已知陷阱影响的技术。特别是，它们专注于间接对角化并表现出完整问题的独特性质。在包容性方面，重点在于对时间和空间有限的概率和量子计算的有效经典模拟。教育目标包括开发伪随机性和去随机化以及量子计算的研究生课程。在本科阶段，研究人员计划进一步将离散结构整合到核心课程中。