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

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

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.