AF: Medium: Collaborative Research: Hardness in Polynomial Time

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

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.