Small Promise CSPs that reduce to large CSPs

DOI10.46298/LMCS-18(3:25)2022MaRDI QIDQ5043583zbMATH OpenOpenAlexFDO

Authors Alexandr Kazda, Peter Mayr, D. N. Zhuk

Publication date 6 October 2022

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

sandwichdigraphconstraint satisfaction problempromise constraint satisfaction problemrelational structure homomorphism

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Recommendations

• Sandwiches for promise constraint satisfaction
• On the reduction of the CSP dichotomy conjecture to digraphs
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
• A finer reduction of constraint problems to digraphs

Cites work

• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 7724184 (Why is no real title available?)
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Algebraic Approach to Promise Constraint Satisfaction
• On the complexity of H-coloring
• Sandwiches for promise constraint satisfaction
• The Complexity of Near-Optimal Graph Coloring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of satisfiability problems
• \((2+\varepsilon)\)-Sat is NP-hard

This page was built for publication: Small Promise CSPs that reduce to large CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5043583)