Lower bounds for prams over Z
| Autor: | Pellissier, Luc, Seiller, Thomas |
|---|---|
| Přispěvatelé: | École polytechnique (X), Automatisation et ReprésenTation: fOndation du calcUl et de la déducTion (PARTOUT), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Paris-Nord (LIPN), Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.2: Modes of Computation/F.1.2.3: Parallelism and concurrency
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS] ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.3: Complexity Measures and Classes/F.1.3.3: Relations among complexity classes [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG] [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] ACM: G.: Mathematics of Computing ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.2: Semantics of Programming Languages |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|