Strong partial clones and the time complexity of SAT problems
From MaRDI portal
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
- 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
Cites work
- 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
- A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
- A low and a high hierarchy within NP
- Basics of Galois Connections
- Can you beat treewidth?
- Classifying the Complexity of Constraints Using Finite Algebras
- Closed systems of functions and predicates
- Dichotomy on intervals of strong partial Boolean clones
- Function Algebras on Finite Sets
- Hard constraint satisfaction problems have hard gaps at location 1
- Hard tiling problems with simple tiles
- scientific article; zbMATH DE number 3972929 (Why is no real title available?)
- scientific article; zbMATH DE number 1953201 (Why is no real title available?)
- scientific article; zbMATH DE number 6028115 (Why is no real title available?)
- scientific article; zbMATH DE number 3336786 (Why is no real title available?)
- Lower bounds based on the exponential time hypothesis
- Mathematical Foundations of Computer Science 2003
- Mathematical Foundations of Computer Science 2005
- Non-dichotomies in Constraint Satisfaction Complexity
- On some closed classes in partial two-valued logic
- On the algebraic structure of combinatorial problems
- On the complexity of k-SAT
- On the limits of sparsification
- On the Structure of Polynomial Time Reducibility
- Partition into triangles on bounded degree graphs
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- The algebras of partial functions and their invariants
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The complexity of satisfiability problems
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- Weak bases of Boolean co-clones
- Which problems have strongly exponential complexity?
Cited in
(19)- Which problems have strongly exponential complexity?
- CNF satisfiability in a subspace and related problems
- 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
- General lower bounds and improved algorithms for infinite-domain CSPs
- A preliminary investigation of satisfiability problems not harder than 1-in-3-SAT
- On moderately exponential time for SAT
- Why are CSPs based on partition schemes computationally hard?
- Testing the Complexity of a Valued CSP Language
- Time complexity of constraint satisfaction via universal algebra
- A dichotomy theorem for the inverse satisfiability problem
- scientific article; zbMATH DE number 7310100 (Why is no real title available?)
- Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
- A survey on the fine-grained complexity of constraint satisfaction problems based on partial polymorphisms
- A note on clustering aggregation for binary clusterings
- Algebraic global gadgetry for surjective constraint satisfaction
- The complexity of the distributed constraint satisfaction problem
- Quantifiers closed under partial polymorphisms
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)
