Strong partial clones and the time complexity of SAT problems
From MaRDI portal
(Redirected from Publication:340559)
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)
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
- 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?)
- 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
- 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 Structure of Polynomial Time Reducibility
- On the algebraic structure of combinatorial problems
- On the complexity of \(k\)-SAT
- On the limits of sparsification
- Partition into triangles on bounded degree graphs
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- 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
- Weak bases of Boolean co-clones
- Which problems have strongly exponential complexity?
Cited in
(18)- scientific article; zbMATH DE number 7310100 (Why is no real title available?)
- A note on clustering aggregation for binary clusterings
- CNF satisfiability in a subspace and related problems
- Algebraic global gadgetry for surjective constraint satisfaction
- A preliminary investigation of satisfiability problems not harder than 1-in-3-SAT
- The complexity of the distributed constraint satisfaction problem
- A dichotomy theorem for the inverse satisfiability problem
- Time complexity of constraint satisfaction via universal algebra
- Which problems have strongly exponential complexity?
- Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
- Testing the Complexity of a Valued CSP Language
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- General lower bounds and improved algorithms for infinite-domain CSPs
- Why are CSPs based on partition schemes computationally hard?
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- scientific article; zbMATH DE number 7536562 (Why is no real title available?)
- Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
- 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)
