2 citations · 2 across the 4 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
Leonid Dorochko, Michał Wrona
Feder-Vardi conjecture, which proposed that every finite-domain Constraint Satisfaction Problem (CSP) is either in P or it is NP-complete, has been solved independently by Bulatov…
cs.CC2021★ 2 cited
The complete classification for quantified equality constraints
Dmitriy Zhuk, Barnaby Martin, Michal Wrona
We prove that QCSP is PSpace-complete, settling a question open for more than ten years. This completes the complexity classification for the QCSP…