Is there an algebraic proof for P ≠ NC? (extended abstract)
Ketan Mulmuley · 1997
We continue our study [27] of lower bounds on par-aHel complexity via an algebraic approach.First, we give a further application of our general lower bound [27] on parallel complexity of a general optimization problem in the PRAM model without bit operations.We show that, for some large enough constant b, the s-t-mincut problem for weighted undirected graphs with n vertices cannot be solved in this model, deterministically or with randomization, within &/b time using 2@/b processors; this is so even if we restrict every edge-capacity to be a nonnegative integer of bitlength at most anz for some large enough constant a. Parallel complexity of this problem was wide open.It was neither known to be P-complete nor was it known to be in (R) NC; we believe our approach may be used to study parallel complexity of many such problems.Second, and most important, we examine the bearing of our lower bounds and techniques on the P # NC conjecture, and in particular, on the possibility of an algebraic proof for it.It turns out that our techniques are insufficient in this regard because they have a fundamental limitation.But a closer analysis of this limitation also suggests what an algebraic proof of P # NC ought to exploit: it should somehow use properties of determinantal or similar rings and varieties in a deep way.This, in conjunction with our lower bounds in a restricted, yet realistic PRAM model, suggests that the algebraic approach, though seemingly quite hard, may be a right one for this problem.