PRAMs over integers do not compute maxflow efficiently

Luc Pellissier (1) , Thomas Seiller (2)

1 LACL - Laboratoire d'Algorithmique Complexité et Logique
2 LIPN - Laboratoire d'Informatique de Paris-Nord

This paper presents a new semantic method for proving lower bounds in computational complexity. We use it to prove that maxflow, a Ptime-complete problem, is not computable in polylogarithmic time on parallel random access machines (PRAMs) working with integers, showing that the class NC over the integers, the complexity class defined by such machines, is different from Ptime, the standard class of polynomial time computable problems (on, say, a Turing machine). On top of showing this new separation result, we show our method captures previous lower bounds results from the literature: Steele and Yao's lower bounds for algebraic decision trees, Ben-Or's lower bounds for algebraic computation trees, Cucker's proof that NC over the reals is not equal to Ptime over the reals, and Mulmuley's lower bounds for "PRAMs without bit operations".

Domaines: Complexité [cs.CC]; Logique en informatique [cs.LO]; Systèmes dynamiques [math.DS]; Géométrie algébrique [math.AG]

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