Perspectives on dynamic complexity theory

动态复杂性理论的观点

• 批准号: 532727578
• 负责人: Professor Dr. Thomas Zeume
• 金额: --
• 依托单位: Arbeitsgruppe Logik und Formale Verifikation
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/532727578?language=en
• 关键词: Perspectives; dynamic; complexity; theory

Very fast, parallel, dynamic algorithms have been intensely explored over the last decades from the perspective of dynamic complexity theory. Such algorithms are surprisingly powerful: among others, it was recently shown that the transitive closure of graphs can be maintained in constant parallel time dynamically. While there has been significant progress in algorithm design in the last years, a much lesser focus was on structural results. The goal of this project is a systematic study of complexity theoretic questions for very fast, parallel, dynamic algorithms. The focus is on exploring (A) barriers for the power of very fast, parallel, dynamic algorithms;(B) the fine-grained structure of small, parallel dynamic complexity classes; and(C) connections between dynamic parallel computational models and to other areas of theoretical computer science.

在过去的几十年里，从动态复杂性理论的角度出发，人们对快速、并行、动态的算法进行了深入的研究。这些算法令人惊讶地强大：其中，最近有研究表明，图的传递闭包可以动态地保持在恒定的并行时间内。虽然过去几年在算法设计方面取得了重大进展，但对结构结果的关注要少得多。这个项目的目标是系统地研究快速、并行、动态算法的复杂性理论问题。重点是探索(A)快速、并行、动态算法的能力障碍；(B)小型并行动态复杂类的细粒度结构；以及(C)动态并行计算模型与理论计算机科学的其他领域之间的联系。