Classifying the Complexity of Constraints Using Finite Algebras
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Universal algebra and hardness results for constraint satisfaction problems
- Affine systems of equations and counting infinitary logic
- Maximal infinite-valued constraint languages
- Minimization of locally defined submodular functions by optimal soft arc consistency
- Determining the consistency of partial tree descriptions
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- A surprising permanence of old motivations (a not-so-rigid story)
- On the algebraic structure of combinatorial problems
- Constraints and universal algebra
- Binary constraint satisfaction problems defined by excluded topological minors
- Tropically convex constraint satisfaction
- Axiomatisability and hardness for universal Horn classes of hypergraphs
- Towards a characterization of constant-factor approximable finite-valued CSPs
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
- The power of propagation: when GAC is enough
- The wonderland of reflections
- On singleton arc consistency for CSPs defined by monotone patterns
- On bijunctive predicates over a finite set
- Constants and finite unary relations in qualitative constraint reasoning
- Implementing a test for tractability
- A new tractable class of constraint satisfaction problems
- Low-level dichotomy for quantified constraint satisfaction problems
- The complexity of problems for quantified constraints
- On rainbow-free colourings of uniform hypergraphs
- Galois connections for patterns: an algebra of labelled graphs
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- On a stronger reconstruction notion for monoids and clones
- A tetrachotomy of ontology-mediated queries with a covering axiom
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- On Maltsev digraphs
- Constraint satisfaction problems over semilattice block Mal'tsev algebras
- The \(C_{k}\)-extended graft construction
- Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- A quasi-Mal'cev condition with unexpected application.
- Commutative idempotent groupoids and the constraint satisfaction problem.
- Domain permutation reduction for constraint satisfaction problems
- On planar valued CSPs
- Majority constraints have bounded pathwidth duality
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- The complexity of soft constraint satisfaction
- Complexity of clausal constraints over chains
- Combinatorial problems raised from 2-semilattices
- Decidability of absorption in relational structures of bounded width.
- Dichotomy for finite tournaments of mixed-type
- CSP for binary conservative relational structures
- An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains
- Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
- Tractability in constraint satisfaction problems: a survey
- Structural decompositions for problems with global constraints
- Complexity classifications of Boolean constraint satisfaction problems
- Constraint satisfaction problems and finite algebras
- The constraint satisfaction problem and universal algebra
- Robustly solvable constraint satisfaction problems
- Minimum cost homomorphisms with constrained costs
- On algebras with many symmetric operations
- CSP dichotomy for special polyads
- Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs
- The complexity of problems connected with two-element algebras
- Is polynomial time choiceless?
- The complexity of constraint satisfaction problems (invited talk)
- On finite Taylor algebras
- Reconstructing the topology of clones
- On Maltsev digraphs
- On the CSP Dichotomy Conjecture
- Constraint Satisfaction Parameterized by Solution Size
- Dualities and algebras with a near-unanimity term
- On the complexity of the model checking problem
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- The Complexity of Counting Quantifiers on Equality Languages
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- On singleton arc consistency for CSPs defined by monotone patterns
- Surjective \texttt{H}-colouring over reflexive digraphs
- Approximability of the Maximum Solution Problem for Certain Families of Algebras
- CSP dichotomy for special triads
- Strong partial clones and the time complexity of SAT problems
- On Planar Boolean CSP
- A Galois connection for valued constraint languages of infinite size
- Algebraic properties of valued constraint satisfaction problem
- Sherali-Adams relaxations for valued CSPs
- Necessary conditions for tractability of valued CSPs
- Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
- Non-dichotomies in Constraint Satisfaction Complexity
- Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
- Varieties with few subalgebras of powers
- List-homomorphism problems on graphs and arc consistency
- Enumerating homomorphisms
- Closure properties of constraints
- scientific article; zbMATH DE number 1944123 (Why is no real title available?)
- Solving order constraints in logarithmic space
- The complexity of surjective homomorphism problems-a survey
- New tractable classes from old
- scientific article; zbMATH DE number 1497884 (Why is no real title available?)
- Colouring, constraint satisfaction, and complexity
- Proof Complexity Meets Algebra
- A dichotomy for first-order reducts of unary structures
- The language of stratified sets is confluent and strongly normalising
- Parameterized complexity of the workflow satisfiability problem
This page was built for publication: Classifying the Complexity of Constraints Using Finite Algebras
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5317171)
