Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951255 | Journal of Computer and System Sciences | 2017 | 27 Pages |
Abstract
Improving exact exponential-time algorithms for NP-complete problems is an expanding research area. Unfortunately, general methods for comparing the complexity of such problems are sorely lacking. In this article we study the complexity of SAT(S) with reductions increasing the amount of variables by a constant (CV-reductions) or a constant factor (LV-reductions). Using clone theory we obtain a partial order ⤠on languages such that SAT(S) is CV-reducible to SAT(Sâ²) if Sâ¤Sâ². With this ordering we identify the computationally easiest NP-complete SAT(S) problem (SAT({R})), which is strictly easier than 1-in-3-SAT. We determine many other languages in ⤠and bound their complexity in relation to SAT({R}). Using LV-reductions we prove that the exponential-time hypothesis is false if and only if all SAT(S) problems are subexponential. This is extended to cover degree-bounded SAT(S) problems. Hence, using clone theory, we obtain a solid understanding of the complexity of SAT(S) with CV- and LV-reductions.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Peter Jonsson, Victor Lagerkvist, Gustav Nordh, Bruno Zanuttini,