20 citations · 85 across the 19 of their papers we have counts for
Showing 2018 · cs.CCShow all
2 papers · 2 filters
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★ 20 cited
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…