Two-element structures modulo primitive positive constructability

DOI10.1007/s00012-020-0647-8zbMath1477.08003arXiv1905.12333OpenAlexW3015111182MaRDI QIDQ2310436

Albert Vucaj, Manuel Bodirsky

Publication date: 6 April 2020

Published in: Algebra Universalis (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1905.12333

zbMATH Keywords

clonesBoolean structurescomplexity of Boolean constraint satisfaction problemsheight-one identitylinear Maltsev conditionminor-preserving mapsprimitive positive construction

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Equational logic, Mal'tsev conditions (08B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Operations and polynomials in algebraic structures, primal algebras (08A40)

Related Items (2)

Submaximal clones over a three-element set up to minor-equivalence ⋮ Smooth digraphs modulo primitive positive constructability and cyclic loop conditions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(H\)-coloring dichotomy revisited
• The complexity of satisfiability problems: Refining Schaefer's theorem
• On the complexity of H-coloring
• The wonderland of reflections
• Taylor's modularity conjecture and related problems for idempotent varieties
• On \(n\)-permutable congruences
• The lattice of interpretability types of varieties
• On Malcev conditions
• The complexity of satisfiability problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

This page was built for publication: Two-element structures modulo primitive positive constructability