课题基金 / 基金详情

Complexity Bounds in Parallel Computation

Complexity Bounds in Parallel Computation
并行计算的复杂性界限
批准号:
8709818
负责人:
Michael Fischer
金额:
$7.8万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
1987
资助国家:
美国
项目状态:
已结题
起止时间:
1987-08-01 至 1990-01-31

项目摘要

项目成果

Michael Fischer的其他基金

相似基金

相关文献

中文摘要
翻译
最近提出了一种新的并行复杂性代数方法, 通过巴林顿等调查人员的工作, 拉兹博罗夫和斯摩棱斯基。 在这样的工作中, 置换群和域上的多项式环 不定式的素数阶 假设是幂等的。 私家侦探们正在调查 并行计算通过分析这种相关的代数 结构. 他们还开发了一种新的计算模型, 他们 所谓的“安全存储机”,定期失去所有,但 恒定的记忆量。 正在进行的是 语言和谓词的类别,可通过 这个新模型。 在理论计算机科学界, 探索新发展的代数观的问题, 并行计算 PI带来了一个广泛而强大的集体, 这项研究的背景。
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
HDNS-I: Infrastructure for Knowledge Linkages from Ethnography of World Societies
  • 批准号:
    2024286
  • 项目类别:
    Standard Grant
  • 资助金额:
    $105.5万
  • 财政年份:
    2020
  • 负责人:
    Michael Fischer
  • 依托单位:
Dissertation Grant: Antibiotic Resistance, Planetary Crisis, and Bacteriophage Futures in the 21st Century
Legal Innovation in Papua New Guinea
  • 批准号:
    ES/J012300/1
  • 项目类别:
    Research Grant
  • 资助金额:
    $18.85万
  • 财政年份:
    2012
  • 负责人:
    Michael Fischer
  • 依托单位:
Doctoral Dissertation Spinning Climate Change: How Social Groups use Media, Science, and PR to Engage the American Public
海外基金