论文标题
简单从公式-SAT减少到标记图和子树的模式匹配
Simple Reductions from Formula-SAT to Pattern Matching on Labeled Graphs and Subtree Isomorphism
论文作者
论文摘要
CNF公式的满足性问题（CNF-SAT）已减少为P中的许多基本问题，以证明在强烈的指数时间假设（SETH）下是紧密的下限。最近，Abboud，Hansen，Vassilevska W.和Williams（Stoc 16）以及后来的Abboud和Bringmann（ICALP 18）的作品提出了基于Boolean Formula Explianiable（Formula-SAT）的硬度的下限。与CNF-SAT的通常减少相比，配方奶粉的减少具有两个优势：（1）对公式-SAT硬度的猜想可以说，比CNF-SAT的猜想更合理，并且（2）这些降低甚至在问题上范围的对数方面的后果也会产生后果。 在这里，我们从公式-SAT下降低了两个问题：标记图（PMLG）和子树同构上的模式匹配。以前从公式-SAT降低的是序列对齐问题，例如编辑距离，LCS和Frechet距离，并且需要进行一些技术工作。本文使用类似于以前使用的想法，但在更简单的环境中，有助于说明基础技术的最显着特征。
The CNF formula satisfiability problem (CNF-SAT) has been reduced to many fundamental problems in P to prove tight lower bounds under the Strong Exponential Time Hypothesis (SETH). Recently, the works of Abboud, Hansen, Vassilevska W. and Williams (STOC 16), and later, Abboud and Bringmann (ICALP 18) have proposed basing lower bounds on the hardness of general boolean formula satisfiability (Formula-SAT). Reductions from Formula-SAT have two advantages over the usual reductions from CNF-SAT: (1) conjectures on the hardness of Formula-SAT are arguably much more plausible than those of CNF-SAT, and (2) these reductions give consequences even for logarithmic improvements in a problems upper bounds. Here we give tight reductions from Formula-SAT to two more problems: pattern matching on labeled graphs (PMLG) and subtree isomorphism. Previous reductions from Formula-SAT were to sequence alignment problems such as Edit Distance, LCS, and Frechet Distance and required some technical work. This paper uses ideas similar to those used previously, but in a decidedly simpler setting, helping to illustrate the most salient features of the underlying techniques.
