Lower Bound Arguments in Machine Based Complexity Theory

基于机器的复杂性理论中的下界参数

• 批准号: 8703889
• 负责人: Wolfgang Maass
• 金额: $ 5.25万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-07-15 至 1990-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8703889&HistoricalAwards=false
• 关键词: Lower; Bound; Arguments; Machine; Based

Mathematical arguments are being developed for proving lower bounds on the computation time and on other resources in machine based complexity theory. Combinatorial methods are being explored for answering a number of fundamental questions about important methods for both sequential and parallel computers. Among the mdoels considered are Turing machines, random access machines, branching programs, and circuits. Lower bound results are important in the science of computing for at least two major reasons: (1) they allow evaluation and comparison of various computational models that reflect interesting aspects of currently existing computers and of potential future computers; and (2) they allow comparisons of the use of computational resources by currently known algorithms with theoretically established optimal limits. Thus lower bound results may indicate where room for improvement lies in both computational models and in existing algorithms.

在基于机器的复杂性理论中，正在开发数学论证来证明计算时间和其他资源的下限。人们正在探索组合方法，以回答有关顺序和并行计算机的重要方法的一些基本问题。考虑的模型包括图灵机、随机存取机、分支程序和电路。下限结果在计算科学中很重要，至少有两个主要原因：(1)它们允许对反映当前现有计算机和潜在未来计算机的有趣方面的各种计算模型进行评估和比较；(2)它们允许将当前已知算法对计算资源的使用与理论上建立的最佳限制进行比较。因此，下限结果可能表明在计算模型和现有算法中存在改进的空间。