Strong partial clones and the time complexity of SAT problems

DOI10.1016/j.jcss.2016.07.008zbMath1353.68133OpenAlexW2519743841MaRDI QIDQ340559

Peter Jonsson, Victor Lagerkvist, Bruno Zanuttini, Gustav Nordh

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

zbMATH Keywords

computational complexityuniversal algebrasatisfiability problemssubexponential timeclone theory

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 (10)

Unnamed Item ⋮ Unnamed Item ⋮ General lower bounds and improved algorithms for infinite-domain CSPs ⋮ Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms ⋮ Testing the Complexity of a Valued CSP Language ⋮ Time Complexity of Constraint Satisfaction via Universal Algebra ⋮ CNF satisfiability in a subspace and related problems ⋮ A Dichotomy Theorem for the Inverse Satisfiability Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hard constraint satisfaction problems have hard gaps at location 1
• A low and a high hierarchy within NP
• On the algebraic structure of combinatorial problems
• Which problems have strongly exponential complexity?
• Dichotomy on intervals of strong partial Boolean clones
• Weak bases of Boolean co-clones
• Closed systems of functions and predicates
• On the Limits of Sparsification
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Partition into Triangles on Bounded Degree Graphs
• Non-dichotomies in Constraint Satisfaction Complexity
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• On some closed classes in partial two-valued logic
• The algebras of partial functions and their invariants
• On the Structure of Polynomial Time Reducibility
• Classifying the Complexity of Constraints Using Finite Algebras
• Function Algebras on Finite Sets
• The complexity of satisfiability problems
• A full derandomization of schöning's k-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
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• On the complexity of \(k\)-SAT
• Hard tiling problems with simple tiles

This page was built for publication: Strong partial clones and the time complexity of SAT problems