AF:Small: Applications of AP-free sets and derandomization

AF:Small：无 AP 集和去随机化的应用

• 批准号: 1017597
• 负责人: Dieter van Melkebeek
• 金额: $ 49.99万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-15 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1017597&HistoricalAwards=false
• 关键词: AF; Small; Applications; AP; free

This project falls within the discipline of computational complexity, which studies the power and limitations of efficient computation. The area develops models that represent the various capabilities of digital computing devices. It aims to determine which transformations can be realized in such a way that the amount of time, memory space, and other resources scale moderately with the input size.Of central importance is the class of so-called NP-complete problems. The latter contains thousands of computational problems from all branches of science and engineering that have been shown equivalent in the sense that an efficient algorithm for one implies such an algorithm for all. The P vs NP question asks whether efficient algorithms exist for these problems. It constitutes the main open question in theory of computing and is one of the seven millennium prize problems proposed by the Clay Mathematics Institute as grand challenges for the 21st century. A positive answer would open up tremendous possibilities that would affect most human endeavors. On the other hand, it would also yield a way to break the cryptographic systems that are currently in use and, in fact, imply the impossibility of secure communication over the internet.This project fits into the quest to settle that fundamental and important problem. In particular, it establishes a tight connection between that question and the amount by which instances of NP-complete problems can be efficiently compressed without affecting their solvability.If P=NP, then NP-complete decision problems can be efficiently compressed to a single bit. On the other hand, under a hypothesis that is somewhat stronger than PNP, the PI has established that NP-complete problems like satisfiability and vertex cover do not allow any nontrivial amount of compression. The approach hinges on the existence of high-density subsets of the integers without arithmetic progressions of length 3. This project further develops that approach and investigates its implications for other computational parameters of interest. The project also involves a systematic study of the use of high-density subsets of the integers without arithmetic progressions of certain lengths in computational complexity, and the development of new applications.The above construction handles deterministic compression schemes. For cryptographic and other reasons the extension to the randomized setting is of interest. One possible approach involves derandomization. In this context the project investigates the potential of typically-correct derandomization, where one aims for efficient deterministic simulations that behave correctly on most but not necessarily all inputs of any given length.

该项目属于计算复杂性的学科，该学科研究了有效计算的能力和局限性。该区域开发了代表数字计算设备各种功能的模型。它旨在以这样的方式确定可以实现哪些转换的时间，内存空间和其他资源量表，以输入大小为中心的重要性是所谓的NP-Complete问题类别。后者包含来自科学和工程的所有分支的数千个计算问题，这些计算问题在某种意义上已经表现出了等效的，即一种有效的算法意味着所有人的算法。 P与NP问题询问这些问题是否存在有效的算法。它构成了计算理论中的主要开放问题，是克莱数学研究所提出的七个千年奖项问题之一，作为21世纪的巨大挑战。一个积极的答案将打开会影响大多数人类努力的巨大可能性。另一方面，这也将产生一种打破当前正在使用的密码系统的方法，实际上意味着无法通过互联网进行安全通信。该项目适合解决这个基本和重要的问题。特别是，它在该问题与NP完整问题的实例之间建立了紧密的联系，而无需影响其解决方案。另一方面，在一个比PNP更强大的假设下，PI确定NP完整的问题（例如Esaflesibility anderiable和顶点覆盖率）不允许任何非平地的压缩量。该方法取决于整数的高密度子集而没有长度3的算术进程。该项目进一步发展了方法，并研究了其对其他感兴趣的计算参数的影响。该项目还涉及对整数的高密度子集使用的系统研究，而没有计算复杂性某些长度的算术进行算术和新应用的开发。上面的构造处理确定性压缩方案。由于密码和其他原因，对随机设置的扩展是值得关注的。一种可能的方法涉及降低。在这种情况下，该项目研究了典型纠正范围化的潜力，其中一个旨在进行有效的确定性模拟，这些模拟在大多数但不一定是任何给定长度的所有输入上都正确地行为。