Unifying lower bounds for algebraic machines, semantically
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2018
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913548997754880 |
|---|---|
| author | Seiller, Thomas Pellissier, Luc Léchine, Ulysse |
| author_facet | Seiller, Thomas Pellissier, Luc Léchine, Ulysse |
| contents | This paper presents a new abstract method for proving lower bounds in computational complexity. Based on the notion of topological and measurable entropy for dynamical systems, it is shown to generalise three previous lower bounds results from the literature in algebraic 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 real numbers. This improves, albeit slightly, on a result of Mulmuley since the class of machines considered extends the class "prams without bit operations", making more precise the relationship between Mulmuley's result and similar lower bounds on real prams.
More importantly, we show our method captures previous lower bounds results from the literature, thus providing a unifying framework for "topological" proofs of lower bounds: Steele and Yao's lower bounds for algebraic decision trees, Ben-Or's lower bounds for algebraic computation trees, Cucker's proof that NC is not equal to Ptime in the real case, and Mulmuley's lower bounds for "prams without bit operations". |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1811_06787 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Unifying lower bounds for algebraic machines, semantically Seiller, Thomas Pellissier, Luc Léchine, Ulysse Computational Complexity Logic in Computer Science 68Q17, 68Q15, 68Q09, 68Q55 This paper presents a new abstract method for proving lower bounds in computational complexity. Based on the notion of topological and measurable entropy for dynamical systems, it is shown to generalise three previous lower bounds results from the literature in algebraic 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 real numbers. This improves, albeit slightly, on a result of Mulmuley since the class of machines considered extends the class "prams without bit operations", making more precise the relationship between Mulmuley's result and similar lower bounds on real prams. More importantly, we show our method captures previous lower bounds results from the literature, thus providing a unifying framework for "topological" proofs of lower bounds: Steele and Yao's lower bounds for algebraic decision trees, Ben-Or's lower bounds for algebraic computation trees, Cucker's proof that NC is not equal to Ptime in the real case, and Mulmuley's lower bounds for "prams without bit operations". |
| title | Unifying lower bounds for algebraic machines, semantically |
| topic | Computational Complexity Logic in Computer Science 68Q17, 68Q15, 68Q09, 68Q55 |
| url | https://arxiv.org/abs/1811.06787 |