Strong partial clones and the time complexity of SAT problems
DOI10.1016/J.JCSS.2016.07.008zbMATH Open1353.68133OpenAlexW2519743841MaRDI QIDQ340559FDOQ340559
Authors: Peter Jonsson, Victor Lagerkvist, Gustav Nordh, Bruno Zanuttini 
Publication date: 14 November 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-171234
Recommendations
- Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- A preliminary investigation of satisfiability problems not harder than 1-in-3-SAT
- On the complexity of \(k\)-SAT
- On problems as hard as CNF-SAT
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70)
Cites Work
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Title not available (Why is that?)
- Which problems have strongly exponential complexity?
- Can you beat treewidth?
- Non-dichotomies in Constraint Satisfaction Complexity
- On the Structure of Polynomial Time Reducibility
- Lower bounds based on the exponential time hypothesis
- Classifying the Complexity of Constraints Using Finite Algebras
- Function Algebras on Finite Sets
- The complexity of satisfiability problems
- On the complexity of \(k\)-SAT
- On the algebraic structure of combinatorial problems
- The algebras of partial functions and their invariants
- Title not available (Why is that?)
- Closed systems of functions and predicates
- Title not available (Why is that?)
- On some closed classes in partial two-valued logic
- Title not available (Why is that?)
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- Hard tiling problems with simple tiles
- A low and a high hierarchy within NP
- Dichotomy on intervals of strong partial Boolean clones
- Weak bases of Boolean co-clones
- On the limits of sparsification
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Partition into triangles on bounded degree graphs
- A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
- Mathematical Foundations of Computer Science 2003
- Mathematical Foundations of Computer Science 2005
- 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
- Basics of Galois Connections
- Hard constraint satisfaction problems have hard gaps at location 1
Cited In (18)
- A note on clustering aggregation for binary clusterings
- Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
- Title not available (Why is that?)
- Time complexity of constraint satisfaction via universal algebra
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Algebraic global gadgetry for surjective constraint satisfaction
- Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
- Why are CSPs based on partition schemes computationally hard?
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- CNF satisfiability in a subspace and related problems
- Which problems have strongly exponential complexity?
- Testing the Complexity of a Valued CSP Language
- The complexity of the distributed constraint satisfaction problem
- A dichotomy theorem for the inverse satisfiability problem
- Title not available (Why is that?)
- A preliminary investigation of satisfiability problems not harder than 1-in-3-SAT
- General lower bounds and improved algorithms for infinite-domain CSPs
- On moderately exponential time for SAT
This page was built for publication: Strong partial clones and the time complexity of SAT problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q340559)
