Lower Bound Arguments in Machine Based Complexity Theory

点击翻译按钮获取中文摘要

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.