Lower Bounds in Parallel Complexity

理论计算机科学中最基本的问题之一，可能仅次于P与NP问题的重要性，是P与NC问题。PI的早期工作表明，许多重要的组合优化问题，如最小成本流和最大流，在没有位操作的PRAM模型中没有快速并行算法；这类似于通常的PRAM模型，主要区别在于处理器的指令集不包含任何位操作。由于最大流和最小费用流问题是P-完全问题，即使在假设P-NC的无约束PRAM模型中，它们也没有快速并行算法。结果的意义在于，可以无条件地证明这一点，也就是说，不需要假设PNC，在一个对所考虑的问题来说是自然和现实的模型中。事实上，不带位运算的PRAM模型已经被广泛应用于大量代数和加权组合优化问题的并行算法设计中。这些算法包括用于解线性系统的快速并行算法、用于最小权生成树的快速并行算法、最短路径、加权无向图中的全局最小割、阻塞流和最大流、多项式的近似根以及计算几何中的几个问题。因此，我们的下界通过在一个受限但现实的并行计算模型中证明了P-完备性的较弱含义，为P-完备性意味着高并行复杂性的信念提供了具体支持，并为P-NC猜想本身提供了具体的支持。这个项目扩展了这些技术来研究其他几个问题的并行复杂性，这些问题不是已知的或预期是P-完全的，因此，其并行复杂性目前还没有被很好地理解。这些问题包括来自几个不同领域的问题：网络流、拟阵优化、计算几何、数值计算、近似优化等等。统一研究这些问题的并行复杂性，对于并行算法的设计和分析具有重要的实际意义和理论意义。该项目包括深入技术的进一步应用，从代数到复杂性理论中的下限问题。

One of the most fundamental problems in theoretical computer science, perhaps next in importance to only the P vs. NP problem, is the P vs. NC problem. Earlier work by the PI has shown that many important combinatorial optimization problems such as mincost flow and maxflow do not have fast parallel algorithms in a PRAM model without bit operations; this is like the usual PRAM model, the main difference being that the instruction set of the processors does not contain any bit operations. Since the maxflow and mincost-flow problems are P-complete, they do not have fast parallel algorithms even in the unrestricted PRAM model assuming P NC. The significance of the result was in the fact that this could be proved unconditionally, i.e., without assuming P NC, in a model that is natural and realistic for the problems under consideration. In fact, the PRAM model without bit operations has been widely used in practice in the design of parallel algorithms for a large number of algebraic and weighted combinatorial optimization problems. These include fast parallel algorithms for solving linear systems, and for minimum-weight-spanning trees, shortest paths, global mincuts in weighted undirected graphs, blocking flows and max flows, approximate roots of polynomials, and several problems in computational geometry. Thus, our lower bound provided a concrete support for the belief that P-completeness implies high parallel complexity, and for the P NC conjecture itself, by proving its weaker implications in a restricted, but realistic parallel model of computation. This project extends these techniques to investigate parallel complexity of several other problems that are not known to be, or expected to be, P-complete, and consequently, whose parallel complexity is not well- understood at present. These include problems from several different areas: network flows, matroidal optimization, computational geometry, numerical computation, approximate optimization, and so fo rth. Investigating parallel complexity of these problems in a unified manner is of considerable practical as well as theoretical significance in the design and analysis of parallel algorithms. The project includes further applications of deep techniques from algebraic to questions of lower bounds in complexity theory.