Small Promise CSPs that reduce to large CSPs

DOI10.46298/LMCS-18(3:25)2022OpenAlexW4292723075MaRDI QIDQ5043583FDOQ5043583

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)

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

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

zbMATH Keywords

sandwichdigraphconstraint satisfaction problempromise constraint satisfaction problemrelational structure homomorphism

Mathematics Subject Classification ID

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

Cites Work

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

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)