Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis

DOI10.1137/1.9781611973105.92zbMath1423.68212OpenAlexW599692955MaRDI QIDQ5741801

Peter Jonsson, Victor Lagerkvist, Bruno Zanuttini, Gustav Nordh

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973105.92

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Operations and polynomials in algebraic structures, primal algebras (08A40)

Related Items (8)

Tractability in constraint satisfaction problems: a survey ⋮ Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis ⋮ Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem ⋮ Weak bases of Boolean co-clones ⋮ Refining complexity analyses in planning by exploiting the exponential time hypothesis ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties

This page was built for publication: Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis