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.