Showing cs.CCShow all
3 papers · 1 filter
cs.CC2024
The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
Kristina Asimi, Libor Barto, Victor Dalmau
We introduce the framework of the left-hand side restricted promise constraint satisfaction problem, which includes problems like approximating clique number of a graph. We study t…
cs.CC2022
Fixed-Template Promise Model Checking Problems
Kristina Asimi, Libor Barto, Silvia Butti
The fixed-template constraint satisfaction problem (CSP) can be seen as the problem of deciding whether a given primitive positive first-order sentence is true in a fixed structure…
cs.CC2020
Finitely (In)tractable Promise Constraint Satisfaction Problems
Kristina Asimi, Libor Barto
The Promise Constraint Satisfaction Problem (PCSP) is a generalization of the Constraint Satisfaction Problem (CSP) that includes approximation variants of satisfiability and graph…