scientific article; zbMATH DE number 7536562
From MaRDI portal
Publication:5863854
Victor Lagerkvist, Lucien Haddad, Miguel Couceiro
Publication date: 3 June 2022
Full work available at URL: https://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-38-number-1-2-2022/mvlsc-38-1-2-p-115-136/
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Operations and polynomials in algebraic structures, primal algebras (08A40) Partial algebras (08A55)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Strong partial clones and the time complexity of SAT problems
- On the algebraic structure of combinatorial problems
- The wonderland of reflections
- Complexity of generalized satisfiability counting problems
- Maximal partial clones with no finite basis
- Dichotomy on intervals of strong partial Boolean clones
- Closed systems of functions and predicates
- The Approximability of Constraint Satisfaction Problems
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- As Close as It Gets
- Complexity of conservative constraint satisfaction problems
- The power of primitive positive definitions with polynomially many variables
- Give Me Another One!
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- An improved exponential-time algorithm for k -SAT
- Enumerating All Solutions for Constraint Satisfaction Problems
- Undirected connectivity in log-space
- The Complexity of Satisfiability of Small Depth Circuits
- The algebras of partial functions and their invariants
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
- Sparsification of SAT and CSP Problems via Tractable Extensions
- Time Complexity of Constraint Satisfaction via Universal Algebra
- On the Subexponential-Time Complexity of CSP
- Bridging between 0/1 and linear programming via random walks
- Classifying the Complexity of Constraints Using Finite Algebras
- Function Algebras on Finite Sets
- The complexity of the counting constraint satisfaction problem
- The complexity of satisfiability problems
- A Simple Algorithm for Mal'tsev Constraints
- A Complete Classification of the Complexity of Propositional Abduction
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- Partial Polymorphisms and Constraint Satisfaction Problems
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- On the complexity of \(k\)-SAT
