论文标题
基于ETH的超线性下限
Superlinear Lower Bounds Based on ETH
论文作者
论文摘要
我们介绍了用于多项式时间问题的超线性条件下限的技术。特别是，我们表明，对于带有m门和log（m）输入的电路（由log-circititsat表示），在本质上是线性的时间无法确定的，除非指数时间假设（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.
