CAREER: Research into the Hardness of Approximation, Probabilistically Checkable Proofs, and Their Connection to Other Areas

经典的NP-完备性理论表明，许多实际感兴趣的优化问题是很难解决的：即没有多项式时间算法的NP-Hard问题(假设P不等于NP)。处理这种NP完全问题的一种流行方法是尝试计算近似解：即其成本在精确解的成本的某个乘性因子内的解。这个项目的重点是证明计算NP-Hard问题的近似解并不比计算精确解容易。所利用的基本思想是NP复杂性类的新的概率定义，该定义基于概率可检查证明(PCP‘s)。该项目的一些主要目标包括：(1)更好地理解NP-Hard优化问题的可逼近性(包括对许多问题的逼近难度进行分类，改进现有关于逼近难度的结果，以及了解这些技术的局限性)；(2)进一步发展PCP理论与密码学之间的联系；(3)改进现有的用纠错码表示数据的方法；(4)简化证明NP的这一新定义所使用的技术。这一职业补助金的教育部分包括：(A)开发核心的本科计算机科学课程(包括计算理论和应用离散数学)；(B)开发一门计算机科学研究生课程和一本涉及PCP和(近似)复杂性理论的相应教材。

The classical theory of NP-completeness shows that many optimization problems of practical interest are hard to solve: i.e., NP-hard problems that have no polynomial-time algorithms (assuming P is not equal to NP). A popular method for dealing with such an NP-complete problem is to try to compute approximate solutions: i.e., solutions whose cost is within some multiplicative factor of the cost of the exact solution. The focus of this project is to demonstrate that computing approximate solutions for NP-hard problems is no easier than computing exact solutions. The underlying idea which is exploited, is that of a new probabilistic definition of the NP complexity class, a definition based on probabilistically checkable proofs (PCP's). Some of the major goals of the project include: (1) To better understand the approximability of NP-hard optimization problems (including cataloging the hardness of approximation of many problems, improving existing results about the hardness of approximation, and understanding the limitation of these techniques); (2) To develop further connections between the theory of PCP's and cryptography; (3) To improve existing ways of representing data by error-correcting codes; (4) To simplify the techniques used in the proof of this new definition of NP. The Educational Component of this CAREER Grant includes: (a) Development of CORE undergraduate computer science courses (including Theory of Computation and Applied Discrete Mathematics); (b) Development of a graduate computer science course and a corresponding text dealing with PCP's and (approximate) complexity theory.