AF: Medium: Collaborative Research: Hardness in Polynomial Time

AF：媒介：协作研究：多项式时间内的硬度

• 批准号: 1514339
• 负责人: Virginia Williams
• 金额: $ 60万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2017-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1514339&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Hardness

A central endeavor of theoretical computer science is to classify computational problems according to the resources (such as running time and storage space) needed to solve them.  Although the field of algorithm design has been highly successful in discovering efficient, polynomial-time algorithms for problems of practical interest, little evidence has been shown for the optimality of most algorithms.  The goal of this project is to build a useful complexity theory for the class of polynomial-time solvable problems (called P), by proving equivalences between problems and proving conditional lower bounds on specific problems, assuming the validity of certain plausible mathematical conjectures.Known lower bounds for specific problems in P are conditioned on some complexity-theoretic assumption such as the (Strong) Exponential Time Hypothesis (concerning the complexity of k-CNF-SAT), the conjecture that dense all-pairs shortest paths (APSP) requires cubic time, or that 3SUM requires quadratic time.  The goals of this project are threefold.  The first goal is to establish conditional lower bounds on problems in diverse areas (such as graph optimization, string matching, geometry, and dynamic data structures) using standard hardness conjectures. The second goal is to search for better hardness conjectures that are both plausible and versatile, and to discover relationships (implications or equivalences) between nominally unrelated conjectures.  The last goal is to investigate the plausibility of these conjectures by attempting to disprove them.The curricular portion of this project involves developing lecture material suitable for introductory algorithms and complexity courses at both the undergraduate and graduate level.

理论计算机科学的一个中心任务是根据解决问题所需的资源（例如运行时间和存储空间）对计算问题进行分类，尽管算法设计领域在发现问题的高效、多项式时间算法方面取得了巨大成功。出于实际兴趣，大多数算法的最优性几乎没有证据表明，该项目的目标是通过证明问题之间的等价性和证明来为多项式时间可解问题（称为 P）建立有用的复杂性理论。有条件的特定问题的下界，假设某些看似合理的数学猜想的有效性。P 中特定问题的已知下界以某些复杂性理论假设为条件，例如（强）指数时间假设（关于 k-CNF-SAT 的复杂性） ），密集全对最短路径（APSP）需要三次时间，或者 3SUM 需要二次时间的猜想。​该项目的目标是第一个目标是使用标准硬度猜想为不同领域（例如图优化、字符串匹配、几何和动态数据结构）的问题建立条件下界，第二个目标是寻找更好的硬度猜想。合理且通用，并发现名义上不相关的猜想之间的关系（含义或等价性）。​最后一个目标是通过尝试反驳这些猜想来调查它们的合理性。该项目的课程部分涉及开发适合本科生和研究生水平的介绍性算法和复杂性课程的讲座材料。