Strong partial clones and the time complexity of SAT problems

作者：

Highlights：

• We investigate the complexity of SAT(⋅) with partial clone theory.

• We identify the computationally easiest NP-complete SAT(⋅) problem.

• We study the time complexity of this problem and relate it to 1-in-3-SAT.

• We relate the easiest SAT(⋅) problem to the exponential-time hypothesis.

摘要

•We investigate the complexity of SAT(⋅) with partial clone theory.•We identify the computationally easiest NP-complete SAT(⋅) problem.•We study the time complexity of this problem and relate it to 1-in-3-SAT.•We relate the easiest SAT(⋅) problem to the exponential-time hypothesis.

论文关键词：Satisfiability problems,Computational complexity,Clone theory,Universal algebra,Subexponential time

论文评审过程：Received 28 October 2014, Revised 6 May 2016, Accepted 23 July 2016, Available online 9 September 2016, Version of Record 14 November 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.07.008