PRAMs over integers do not compute maxflow efficiently

Luc Pellissier (1) , Thomas Seiller (2)

1 UDELAR - Universidad de la República [Montevideo]
2 LIPN - Laboratoire d'Informatique de Paris-Nord

Finding lower bounds in complexity theory has proven to be an extremely difficult task. In this article, we analyze two proofs of complexity lower bound: Ben-Or's proof of minimal height of algebraic computational trees deciding certain problems and Mulmuley's proof that restricted Parallel Random Access Machines (prams) over integers can not decide P-complete problems efficiently. We present the aforementioned models of computation in a framework inspired by dynamical systems and models of linear logic : graphings. This interpretation allows to connect the classical proofs to topological entropy, an invariant of these systems; to devise an algebraic formulation of parallelism of computational models; and finally to strengthen Mulmuley's result by separating the geometrical insights of the proof from the ones related to the computation and blending these with Ben-Or's proof. Looking forward, the interpretation of algebraic complexity theory as dynamical system might shed a new light on research programs such as Geometric Complexity Theory.

Domaines: Complexité [cs.CC]; Logique en informatique [cs.LO]; Systèmes dynamiques [math.DS]

Luc Pellissier, Thomas Seiller. PRAMs over integers do not compute maxflow efficiently. 2018. ⟨hal-01921942v1⟩