Conditional Lower Bounds for Space/Time Tradeoffs
Conditional Lower Bounds for Space/Time Tradeoffs
复制标题
空间/时间权衡的条件下界
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
E. Porat
中科院分区：
文献类型：
--
作者：
Isaac Goldstein;T. Kopelowitz;Moshe Lewenstein;E. Porat
近年来，人们付出了很多努力致力于在解决各种著名问题的算法上实现多项式时间下界。一种用于展示此类下界的有用技术是基于经过充分研究的困难性假设（例如3SUM、APSP、SETH等）有条件地证明它们。这一系列研究有助于更好地理解P类问题内部的复杂性。
一个相关的问题是，在经过初始预处理阶段后，对于为解决某些算法任务而构建的数据结构，要求证明其有条件的空间下界。尽管这个问题具有潜在的重大影响，但在先前的研究中却很少受到关注。
在本文中，我们探讨了这个问题，并令人惊讶地发现，许多已知具有条件多项式时间下界的经过充分研究的难题在涉及空间时也很困难。这种困难表现为数据结构所占用的空间与回答查询所需时间之间的权衡。这种权衡可能是平滑的，也可能存在一个或多个奇异点。
我们揭示了不同空间困难性猜想之间有趣的联系，并给出了匹配的上界。我们还将这些困难性猜想应用于静态和动态问题，并证明了它们的有条件空间困难性。
我们相信，这种新的多项式空间猜想框架在表达许多重要算法问题的多项式空间下界方面能够发挥重要作用。此外，它似乎也有助于从时间角度更好地理解其相应问题的困难性。
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.
A related question asks to prove conditional space lower bounds on data structures that are constructed to solve certain algorithmic tasks after an initial preprocessing stage. This question received little attention in previous research even though it has potential strong impact.
In this paper we address this question and show that surprisingly many of the well-studied hard problems that are known to have conditional polynomial time lower bounds are also hard when concerning space. This hardness is shown as a tradeoff between the space consumed by the data structure and the time needed to answer queries. The tradeoff may be either smooth or admit one or more singularity points.
We reveal interesting connections between different space hardness conjectures and present matching upper bounds. We also apply these hardness conjectures to both static and dynamic problems and prove their conditional space hardness.
We believe that this novel framework of polynomial space conjectures can play an important role in expressing polynomial space lower bounds of many important algorithmic problems. Moreover, it seems that it can also help in achieving a better understanding of the hardness of their corresponding problems in terms of time.