Superlinear Lower Bounds Based on ETH
Superlinear Lower Bounds Based on ETH
复制标题
DOI：
10.4230/lipics.stacs.2022.55
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
András Z. Salamon;Michael Wehar
中科院分区：
文献类型：
--
作者：
András Z. Salamon;Michael Wehar
我们介绍技术证明超线性条件下界多项式时间问题。特别是，我们证明了具有m个门和log（m）输入的电路的CircuitSAT（用log-CircuitSAT表示）在本质线性时间内是不可判定的，除非指数时间假设（ETH）为假并且k-Clique在本质线性时间内是可判定的对于所有固定的k，图的大小。这样的条件下限以前只被证明相对于强指数时间假设（SETH）。因此，我们的研究结果提供了显着的进展，证明无条件的超线性时间复杂性的自然问题的下界在多项式时间。
We introduce techniques for proving superlinear conditional lower bounds for polynomial time problems. In particular, we show that CircuitSAT for circuits with m gates and log(m) inputs (denoted by log-CircuitSAT) is not decidable in essentially-linear time unless the exponential time hypothesis (ETH) is false and k-Clique is decidable in essentially-linear time in terms of the graph's size for all fixed k. Such conditional lower bounds have previously only been demonstrated relative to the strong exponential time hypothesis (SETH). Our results therefore offer significant progress towards proving unconditional superlinear time complexity lower bounds for natural problems in polynomial time.