Exploiting Structured Computations

利用结构化计算

• 批准号: 9002891
• 负责人: Martin Tompa
• 金额: $ 34.96万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-08-15 至 1994-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9002891&HistoricalAwards=false
• 关键词: Exploiting; Structured; Computations

Graph traversal is a fundamental computational problem, not only because it is the natural abstraction of many search problems, but also because its complexity is at the root of important relationships among deterministic, nondeterministic, and probabilistic computations. Significant progress has been made during the last two years toward understanding the complexity of graph traversal. Viewing the problem in its natural structured setting was crucial to most or all of these advances. This project is following a number of approaches to investigate the time and space complexity of graph traversal in structured settings. The goal is to obtain stronger results in the previously studied structured settings, and novel results in substantially richer structured settings. Similarly, structured views of important algebraic problems such as matrix multiplication have been instrumental in advances toward understanding those problems. The project is also investigating the communication and space complexity of these problems, motivated by the importance of communication in parallel and distributed computation.

图遍历是一个基本的计算问题，不仅因为它是许多搜索问题的自然抽象，而且因为它的复杂性是确定性、非确定性和概率计算之间重要关系的根源。 过去两年，在理解图遍历的复杂性方面取得了重大进展。 从自然的结构化环境中看待问题对于大多数或所有这些进步至关重要。 该项目采用多种方法来研究结构化设置中图遍历的时间和空间复杂性。 目标是在先前研究的结构化设置中获得更强的结果，并在更丰富的结构化设置中获得新颖的结果。 同样，矩阵乘法等重要代数问题的结构化视图也有助于理解这些问题。 出于并行和分布式计算中通信的重要性，该项目还在研究这些问题的通信和空间复杂性。