4 citations · 4 across the 2 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2018
The complexity of disjunctive linear Diophantine constraints
Manuel Bodirsky, Barnaby Martin, Marcello Mamino +1
We study the Constraint Satisfaction Problem CSP(A), where A is first-order definable in (Z;+,1) and contains +. We prove such problems are either in P or NP-complete.
cs.CC2018
A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
Manuel Bodirsky, Florent Madelaine, Antoine Mottet
The logic MMSNP is a restricted fragment of existential second-order logic which allows to express many interesting queries in graph theory and finite model theory. The logic was i…