AF: Small: CSPs --- Approximability versus Time

AF：小：CSP --- 近似性与时间

• 批准号: 1319743
• 负责人: Ryan O'Donnell
• 金额: $ 42.62万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-06-01 至 2016-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319743&HistoricalAwards=false
• 关键词: AF; Small; CSPs; Approximability; versus

The proposed research addresses the algorithmic complexity of very basic optimization tasks - network partitioning, solving linear equations, satisfying logical formulas, and other constraint satisfaction problems (CSPs). Previous research on these kinds of problems suggested the existence of either very efficient algorithms yielding solutions of a certain quality, or very inefficient algorithms achieving perfect quality. However recent research, including a newly evolving algorithmic technique called the "SOS method", suggests the possibility of a nontrivial tradeoff between efficiency and quality. Specifically, the work has the following three technical goals:1. Further understand the power and the limitations of the SOS Method.2. Improve the known NP-hardness results for CSPs, with an emphasis on giving evidence against subexponential-time algorithms.3. Find new random families of CSP instances - especially "Small-Set Expansion" or "Unique Games" instances - which seem algorithmically difficult.The research will ultimately have broad impact on the practice of algorithms; more specifically, on developing (and ruling out) truly efficient heuristics for solving constraint satisfaction problems. It is also possible that the research on finding new families of hard-seeming CSP instances may lead to advances in cryptography.

提出的研究解决了非常基本的优化任务的算法复杂性-网络划分、解线性方程、满足逻辑公式和其他约束满足问题(CSP)。以前对这类问题的研究表明，要么存在非常有效的算法来产生某种质量的解，要么存在非常低效的算法来获得完美的质量。然而，最近的研究，包括一种名为“SOS方法”的新发展的算法技术，表明了在效率和质量之间进行权衡的可能性。具体地说，这项工作有以下三个技术目标：1.进一步了解SOS方法的力量和局限性。改进了已知的CSP的NP-难结果，重点是给出了反对次指数时间算法的证据。寻找新的随机CSP实例族--特别是“小集合扩展”或“唯一博弈”实例--它们在算法上似乎很困难。这项研究最终将对算法的实践产生广泛的影响；更具体地说，是开发(和排除)真正有效的启发式算法来解决约束满足问题。寻找新的看似坚硬的CSP实例的研究也有可能导致密码学的进步。