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.