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

这个项目属于计算复杂性的学科，它研究高效计算的能力和局限性。该领域开发代表数字计算设备各种功能的模型。它的目的是确定哪些转换可以以这样一种方式实现，即时间、存储空间和其他资源的数量随输入大小适度调整。其中最重要的是所谓的NP-完全问题。后者包含来自科学和工程所有分支的数千个计算问题，这些问题已被证明是等价的，因为一个人的有效算法意味着所有人都有这样的算法。P与NP问题是问是否存在有效的算法来解决这些问题。它构成了计算理论中的主要悬而未决的问题，也是克莱数学研究所提出的21世纪重大挑战的七个千禧年奖问题之一。一个积极的答案将带来巨大的可能性，这些可能性将影响到大多数人类的努力。另一方面，它也将产生一种方法来打破目前正在使用的密码系统，实际上意味着不可能在互联网上进行安全通信。这个项目符合解决这一根本和重要问题的探索。如果P=NP，则NP-完全决策问题可以被有效地压缩到一位。另一方面，在一个比PNP更强的假设下，PI已经确定了NP-完全问题，如可满足性和顶点覆盖，不允许任何非平凡的压缩。该方法依赖于没有长度为3的算术级数的整数的高密度子集的存在。本项目进一步发展了该方法，并研究了它对其他感兴趣的计算参数的影响。该项目还包括系统地研究如何使用高密度的整数子集，而不使用计算复杂度具有一定长度的算术级数，以及开发新的应用程序。出于加密和其他原因，对随机化设置的扩展是感兴趣的。一种可能的方法是去随机化。在这种背景下，该项目调查了典型正确的去随机化的可能性，其中一个目标是有效的确定性模拟，在大多数但不一定是任何给定长度的所有输入上都正确地行为。

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.