AF: SMALL: On the Complexity of Satisfiable CSPs

复杂性理论是对执行计算任务所需的资源（时间、内存、处理器数量）的研究，其主要目标是将计算问题分类为可行（即可以有效解决的问题）或不可行（即不能有效解决的问题）。概率可检验证明是复杂性理论的一个子领域，它将这一研究扩展到近似问题的领域，并表明对于许多计算任务，甚至提出一个近似的解决方案可能在计算上是不可行的。如今，这一领域的成果也被用于区块链和加密货币等非中心化系统的实际应用中。该项目的目标是进一步发展概率可检验证明理论，并解决该领域新的和长期存在的挑战。该项目结合了计算机科学和数学的各个分支，并可能影响其他科学领域。项目的活动包括课程开发、指导和研讨会组织。更详细地说，本项目侧重于研究可满足约束的满足问题。约束满足问题（简称csp）是复杂性理论中最基本的一类问题。一个问题的实例包括一组待定变量，以及一组施加在这些变量上的约束；目标是找到对变量的赋值，使其满足尽可能多的约束。什么是最好的，最有效的近似算法来解决这个问题，如果一个解满足所有的约束存在？这个项目是由这个元问题驱动的，旨在创造新的工具，并与其他数学领域形成新的联系。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Complexity Theory is the study of resources (time, memory, number of processors) needed to execute computational tasks, whose main goal is to classify computational problems as feasible (i.e., problems that can be solved efficiently) or as infeasible (i.e., problems that cannot be solved efficiently). Probabilistically Checkable Proofs is a sub-area of Complexity Theory that extends this study to the realm of approximation problems and shows that for many computational tasks, even coming up with an approximate solution may be computationally infeasible. Nowadays, results from this area are also used in real-life applications in non-centralized systems such as blockchains and cryptocurrencies. The goal of this project is to further develop the theory of Probabilistically Checkable Proofs and address new, as well as long-standing, challenges in the area. The project combines various branches of computer science and mathematics and may impact other scientific fields. The project's activities include course development, mentoring, and workshop organization. In more detail, this project focuses on studying satisfiable constraint satisfaction problems. The class of constraint satisfaction problems (CSPs in short) is one of the most fundamental classes of problems in complexity theory. An instance of a problem consists of a collection of undetermined variables, as well as a collection of constraints imposed on them; the goal is to find an assignment to the variables that satisfies as many of the constraints as possible. What is the best, most efficient approximation algorithm to this problem, provided that a solution that satisfies all of the constraints exists? This project is driven by this meta question, aiming to create new tools as well as form new connections with other mathematical areas.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.