CAREER: New Directions in Inapproximability and Probabilistically Checkable Proofs

职业：不可近似性和概率可检查证明的新方向

• 批准号: 0833228
• 负责人: Subhash Khot
• 金额: $ 23.99万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-03-31 至 2012-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0833228&HistoricalAwards=false
• 关键词: CAREER; New; Directions; Inapproximability; Probabilistically

The central question studied in theoretical computer science is: how efficiently (fast) can computational problems be solved?While many problems do have efficient algorithms, there is a wide class of important problems (called NP-complete problems) which are very unlikely to have efficient algorithms. In practice however, it may suffice to solve these problems approximately. This research investigates whether approximate solutions to NP-complete problems can be found efficiently, and how good is the quality of approximation. The main contribution of this research is negative results, i.e. proving that for certain NP-complete problems, efficiently finding even approximate solutions is very unlikely. To illustrate the significance of proving such negative results, the investigator proves that it is unlikely to break into a certain cryptosystem, giving a guarantee of its security against malicious attacks. Another related aspect of this research is Proababilistically Checkable Proofs, a method to specify proof formats for mathematical statements, such that the validity of the proof can be checked very efficiently, by looking at only a few places in the proof instead of reading the entire proof. The research has a potential for broader impact in terms of scientific workshops, collaboration between several international researchers, developement of graduate courses, promoting undergraduate research, and advising Ph.D. students. Many computational problems arising in theory and practice are NP-complete. An extensively studied approach to cope with NP-completeness is designing polynomial time algorithms that compute approximately optimal solutions. However, it turns out that for many problems, computing approximate solutions itself is an NP-complete problem, a famous result known as the PCP Theorem, discovered in 1992. In spite of the tremendous body of research that followed this discovery, for many NP-complete problems, there is a gap between the best known approximation result, and the best known inapproximability result. This research focusses on filling this gap by proving tight inapproximability results. The PCP Theorem can also be viewed as a result about proof checking (and that is how it was discovered). It gives a way of specifying proofs for NP-statements such that the validity of the proof can be checked very efficiently. The research investigates constructions of more efficient PCPs, with further applications to inapproximability results. The techniques developed are likely to have new applications to areas like metric embeddings and learning theory. The research has a potential for broader impact in terms of scientific workshops, collaboration between international researchers, developement of graduate courses, promoting undergraduate research and advising Ph.D. students.

理论计算机科学中研究的中心问题是：如何有效地解决计算问题？尽管许多问题确实具有有效的算法，但仍有一系列重要的重要问题（称为NP完整问题），这些问题不太可能具有有效的算法。但是，实际上，大约解决这些问题可能就足够了。这项研究调查了是否可以有效地发现NP完整问题的近似解决方案，以及近似质量的良好程度。这项研究的主要贡献是负面的结果，即证明对于某些NP完整问题，有效地找到近似解决方案的不太可能是极不可能的。为了说明证明这种负面结果的重要性，研究人员证明，它不太可能闯入某个隐秘系统，从而保证其抵抗恶意攻击的安全性。这项研究的另一个相关方面是可靠的可检查证明，这是一种指定数学陈述的证明格式的方法，以便通过仅查看证明中的几个地方而不是阅读整个证明，可以非常有效地检查证明的有效性。这项研究在科学研讨会，几位国际研究人员之间的合作，研究生课程的发展，促进本科研究以及为博士学位提供建议方面具有更广泛的影响。学生。在理论和实践中引起的许多计算问题都是NP完整的。经过广泛研究的方法来应对NP完整性，正在设计计算大约最佳溶液的多项式时间算法。但是，事实证明，对于许多问题，计算近似解决方案本身是一个NP完整问题，即1992年发现的著名结果，称为PCP定理。尽管进行了这一发现之后的大量研究，但对于许多NP完整问题，对于许多NP完全解决问题，但最众所周知的近似结果和最众所周知的Inapproximability Inapproximability却存在差距。这项研究的重点是通过证明严格的不Xibibibility结果来填补这一空白。 PCP定理也可以视为证明检查（这就是发现的方式）。它提供了指定NP统计的证明的方法，以便可以非常有效地检查证明的有效性。该研究调查了更有效的PCP的结构，并进一步应用了不Xibibibility的结果。所开发的技术可能会在公制嵌入和学习理论等领域具有新的应用。这项研究在科学研讨会，国际研究人员之间的合作，研究生课程的发展，促进本科研究和建议博士学位方面具有更广泛影响的潜力。学生。