Complexity Bounds in Parallel Computation

并行计算的复杂性界限

• 批准号: 8709818
• 负责人: Michael Fischer
• 金额: $ 7.8万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-08-01 至 1990-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8709818&HistoricalAwards=false
• 关键词: Complexity; Bounds; Parallel; Computation

A new algebraic approach to parallel complexity has recently been emerging through the work of such investigators as Barrington, Razborov, and Smolensky. In such work use is made of finite permutation groups and also of rings of polynomials over fields of prime order for which the indeterminants are assumed to be idempotent. The PIs are investigating the complexity of parallel computation through the analysis of such associated algebraic structures. They have also developed a new model of computation that they call the "safe storage machine" which periodically loses all but a constant amount of its memory. In progress are characterizations of classes of languages and predicates definable by means of variations of this new model. There is much interest in the theoretical computer science community in the exploration of the newly developed algebraic view of questions in parallel computation. The PIs bring a broad strong collective background to this study.

最近提出了一种新的并行复杂性代数方法， 通过巴林顿等调查人员的工作， 拉兹博罗夫和斯摩棱斯基。 在这样的工作中， 置换群和域上的多项式环 不定式的素数阶 假设是幂等的。 私家侦探们正在调查 通过分析此类相关代数进行并行计算 结构. 他们还开发了一种新的计算模型， 他们 所谓的“安全存储机”，定期失去所有，但 恒定的记忆量。 正在进行的是 语言和谓词的类别，可通过 这个新模型。 在理论计算机科学界， 探索新发展的代数观的问题， 并行计算 PI带来了一个广泛而强大的集体， 这项研究的背景。