Tractable topological computing: Escaping the hardness trap

易于处理的拓扑计算：摆脱硬度陷阱

• 批准号: DP150104108
• 负责人: Prof Benjamin Burton
• 金额: $ 24.5万
• 依托单位: The University of Queensland
• 依托单位国家: 澳大利亚
• 项目类别: Discovery Projects
• 财政年份: 2015
• 资助国家: 澳大利亚
• 起止时间: 2015-01-01 至 2023-06-30
• 项目状态: 已结题
• 来源: https://dataportal.arc.gov.au/RGS/Web/Grants/DP150104108
• 关键词: Tractable; topological; computing; Escaping; hardness

Computational topology is a young and energetic field that uses computers to solve complex geometric problems driven by pure mathematics, and with diverse applications in biology, signal processing and data mining. A major barrier is that many of these problems are thought to be fundamentally and intractably hard. This project aims to defy such barriers for typical real-world inputs by fusing geometric techniques with technologies from the field of parameterised complexity, creating powerful, practical solutions for these problems. It is expected to shed much-needed light on the vast and puzzling gap between theory and practice, and give researchers fast new software tools for large-scale experimentation and cutting-edge computer proofs.

计算拓扑学是一个年轻而充满活力的领域，它使用计算机来解决由纯数学驱动的复杂几何问题，并在生物学，信号处理和数据挖掘中有着广泛的应用。一个主要的障碍是，这些问题中有许多被认为是从根本上难以解决的。该项目旨在通过将几何技术与参数化复杂性领域的技术融合，为这些问题创建强大，实用的解决方案，从而克服典型现实世界输入的障碍。它有望揭示理论与实践之间巨大而令人困惑的差距，并为研究人员提供快速的新软件工具，用于大规模实验和尖端的计算机证明。