Lower Bound Arguments in Machine Based Complexity Theory

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

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.