# A preliminary investigation of satisfiability problems not harder than 1-In-3-SAT

Research output: Contribution to book/conference proceedings/anthology/report › Chapter in book/anthology/report › Contributed › peer-review

## Contributors

## Abstract

The parameterized satisfiability problem over a set of Boolean relations Γ (SAT(Γ)) is the problem of determining whether a conjunctive formula over Γ has at least one model. Due to Schaefer's dichotomy theorem the computational complexity of SAT(Γ), modulo polynomial-time reductions, has been completely determined: SAT(Γ) is always either tractable or NP-complete. More recently, the problem of studying the relationship between the complexity of the NP-complete cases of SAT(Γ) with restricted notions of reductions has attracted attention. For example, Impagliazzo et al. studied the complexity of k-SAT and proved that the worst-case time complexity increases infinitely often for larger values of k, unless 3-SAT is solvable in subexponential time. In a similar line of research Jonsson et al. studied the complexity of SAT(Γ) with algebraic tools borrowed from clone theory and proved that there exists an NP-complete problem SAT(R≠ ≠ ≠01 1/3) such that there cannot exist any NP-complete SAT(Γ) problem with strictly lower worst-case time complexity: The easiest NP-complete SAT(Γ) problem. In this paper we are interested in classifying the NP-complete SAT(Γ) problems whose worst-case time complexity is lower than 1-in-3-SAT but higher than the easiest problem SAT(R≠ ≠ ≠01 1/3 ). Recently it was conjectured that there only exists three satisfiability problems of this form. We prove that this conjecture does not hold and that there is an infinite number of such SAT(Γ) problems. In the process we determine several algebraic properties of 1-in-3-SAT and related problems, which could be of independent interest for constructing exponential-time algorithms.

## Details

Original language | German |
---|---|

Title of host publication | 41st International Symposium on Mathematical Foundations of Computer Science |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 64:1-64:14 |

ISBN (print) | 9783959770163 |

Publication status | Published - 1 Aug 2016 |

Peer-reviewed | Yes |

### Publication series

Series | 41st International Symposium on Mathematical Foundations of Computer Science (MFCS`16) ; Vol. 58 |
---|---|

Volume | 58 |

ISSN | 1868-8969 |

## External IDs

Scopus | 85012869811 |
---|

## Keywords

### Keywords

- Clone Theory, Satisfiability Problems, Universal Algebra