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

constraint satisfaction problemdigraphpromise constraint satisfaction problemrelational structure homomorphismsandwich

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

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

Cited in

(2)

• The school of V. B. Kudryavtsev at the chair of mathematical theory of intelligent systems: traditions and development
• GMSNP and finite structures

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)