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的特定性（例如某些复杂性）（强大的时间）（强大的时间）（强大的时间）（强度）（强大的时间）（强大的时间）（强大的时间）（强大的时间）（强大的时间）（强大的时间）（强大的时间）（强有力），则在特定问题上提供有效的有效性（强有力的）（强大的时间） k-cnf-sat），猜想最短的路径（APSP）需要立方时间，或者3sum需要二次时间。该项目的目标是三倍。第一个目标是使用标准硬度猜想来建立潜水区域（例如图形优化，字符串匹配，几何和动态数据结构）的问题的条件下限。第二个目标是寻找既合理又多功能的更好的硬度猜想，并发现名义上无关协议之间的关系（含义或等价）。最后的目标是通过试图反驳这些协议的合理性。该项目的课程部分涉及开发适合于本科和研究生级别的算法和复杂性课程的讲座材料。