论文标题
部分可观测时空混沌系统的无模型预测
Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
论文作者
论文摘要
我们考虑在节点标记的图形$ g =（v，e）$：给定模式字符串$ p $上的以下字符串匹配问题，确定是否存在$ g $中的路径，其节点标签的串联等于$ p $。这是生物信息学，图形数据库或网络中各种问题的基本原始性。 Backurs和Indyk（Focs 2016）的硬度结果表明，在正交矢量假说（OVH）下，该问题不能比$ O（| e || P |）$时间更好地解决，即使在图表上的各种限制下，这也存在（Equi等，ICTAL。，ICTAL。，ICTAL。，ICTAL。2019）。 在本文中，我们考虑其离线版本，即允许我们索引图表以支持及时的字符串匹配查询的版本。的确，在弦乐社区中，人们相信可以实现次级时间查询，例如以高度多项式索引为代价。 我们反驳了这种信念，表明，在OVH下，没有多项式索引可以支持查询时间$ O（| e |^δ| p |^β）$，其中$Δ<1 $或$β<1 $。我们证明了采用已知的可自我还原技术的紧密约束，例如从动态算法领域，将有条件的下限转化为在线问题的下线版本。 作为侧归因，我们通过减少线性独立组件的概念将该技术形式化，从而简单地证明了我们的结果。作为我们技术的另一个例证，我们还将Backurs和Indyk（STOC 2015）的二次有条件下限转换为在编辑距离下与文本内部的查询字符串匹配的问题。我们为其离线版本获得了类似的紧密二次下限，改善了Cohen-Addad，Feuilloley和Starikovskaya的最新结果（Soda 2019），但边界条件略有不同。
We consider the following string matching problem on a node-labeled graph $G=(V,E)$: given a pattern string $P$, decide whether there exists a path in $G$ whose concatenation of node labels equals $P$. This is a basic primitive in various problems in bioinformatics, graph databases, or networks. The hardness results of Backurs and Indyk (FOCS 2016) imply that this problem cannot be solved in better than $O(|E||P|)$ time, under the Orthogonal Vectors Hypothesis (OVH), and this holds even under various restrictions on the graph (Equi et al., ICALP 2019). In this paper we consider its offline version, namely the one in which we are allowed to index the graph in order to support time-efficient string matching queries. Indeed, it was tantalizing in the string matching community to believe that sub-quadratic time queries can be achieved, e.g. at the cost of a high-degree polynomial-time indexing. We disprove this belief, showing that, under OVH, no polynomial-time index can support querying $P$ in time $O(|E|^δ|P|^β)$, with either $δ< 1$ or $β< 1$. We prove this tight bound employing a known self-reducibility technique, e.g. from the field of dynamic algorithms, which translates conditional lower bounds for an online problem to its offline version. As a side-contribution, we formalize this technique with the notion of linear independent-components reduction, allowing for a simple proof of our result. As another illustration of our technique, we also translate the quadratic conditional lower bound of Backurs and Indyk (STOC 2015) for the problem of matching a query string inside a text, under edit distance. We obtain an analogous tight quadratic lower bound for its offline version, improving the recent result of Cohen-Addad, Feuilloley and Starikovskaya (SODA 2019), but with a slightly different boundary condition.
