Conditional Lower Bounds for Space/Time Tradeoffs
| Autor: | Tsvi Kopelowitz, Moshe Lewenstein, Isaac Goldstein, Ely Porat |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
3SUM
010201 computation theory & mathematics Computer science Space time Line (geometry) 0202 electrical engineering electronic engineering information engineering 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Algorithm Time complexity |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783319621265 WADS |
| DOI: | 10.1007/978-3-319-62127-2_36 |
| Popis: | In recent years much effort has been concentrated towards achieving polynomial time lower bounds on algorithms for solving various well-known problems. A useful technique for showing such lower bounds is to prove them conditionally based on well-studied hardness assumptions such as 3SUM, APSP, SETH, etc. This line of research helps to obtain a better understanding of the complexity inside P. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|