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

DOI10.1137/1.9781611973105.92MaRDI QIDQ5741801zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Victor Lagerkvist, Gustav Nordh, Bruno Zanuttini

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

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

Recommendations

• Strong partial clones and the time complexity of SAT problems
• The complexity of satisfiability problems
• The complexity of satisfiability problems: Refining Schaefer's theorem
• Mathematical Foundations of Computer Science 2005
• A note on SAT algorithms and proof complexity
• On the complexity of k-SAT
• Mathematical Foundations of Computer Science 2005
• Exponential complexity of satisfiability testing for linear-size Boolean formulas
• Algorithms for Sat and upper bounds on their complexity

Cited in

(25)

• Some structural properties of SAT
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Sparsification and subexponential approximation
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• Constructing NP-intermediate problems by blowing holes with parameters of various properties
• Weak bases of Boolean co-clones
• Tractability in constraint satisfaction problems: a survey
• Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
• Precise upper and lower bounds for the monotone constraint satisfaction problem
• Satisfiability certificates verifiable in subexponential time
• On the exact complexity of evaluating quantified k-CNF
• Strong partial clones and the time complexity of SAT problems
• The Complexity of Very Simple Boolean Formulas with Applications
• Satisfiability with Exponential Families
• scientific article; zbMATH DE number 17806 (Why is no real title available?)
• On existential MSO and its relation to ETH
• A preliminary investigation of satisfiability problems not harder than 1-in-3-SAT
• On moderately exponential time for SAT
• On problems as hard as CNF-SAT
• Refining complexity analyses in planning by exploiting the exponential time hypothesis
• Time complexity of constraint satisfaction via universal algebra
• An initial study of time complexity in infinite-domain constraint satisfaction
• On existential MSO and its relation to ETH
• On the complexity of k-SAT

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741801)