Lower Bounds in Parallel Complexity

理论计算机科学中最基本的问题之一，也许仅次于P vs. NP问题，就是P vs. NC问题。 PI的早期工作表明，许多重要的组合优化问题，如mincost flow和maxflow，在没有位操作的PRAM模型中没有快速并行算法;这就像通常的PRAM模型，主要区别在于处理器的指令集不包含任何位操作。 由于最大流和最小成本流问题是P-完全的，它们没有快速的并行算法，即使在无限制的PRAM模型假设P NC。 这个结果的意义在于，这一点可以无条件地证明，即，不假设P NC，在一个模型中，这是自然和现实的问题正在考虑。 实际上，无位操作的PRAM模型在大量代数和加权组合优化问题的并行算法设计中得到了广泛的应用。 这些包括快速并行算法求解线性系统，并为最小重量生成树，最短路径，全球mincuts在加权无向图，阻塞流和最大流量，多项式的近似根，以及计算几何中的几个问题。 因此，我们的下界提供了一个具体的支持的信念，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.