Lower bounds for prams over Z
share
This paper presents a new abstract method for proving lower bounds in computational complexity. Based on the notion of topological entropy for dynamical systems, the method captures four previous lower bounds results from the literature in algebraic complexity. Among these results lies Mulmuley's proof that "prams without bit operations" do not compute the maxflow problem in polylogarithmic time, which was the best known lower bounds in the quest for a proof that NC = Ptime. Inspired from a refinement of Steele and Yao's lower bounds, due to Ben-Or, we strengthen Mulmuley's result to a larger class of machines, showing that prams over integer do not compute maxflow in polylogarithmic time.
READ FULL TEXT