20 citations · 75 across the 44 of their papers we have counts for
Showing 2018 · cs.CCShow all
2 papers · 2 filters
cs.CC2018★ 2 cited
Resolution and the binary encoding of combinatorial principles
Stefan Dantchev, Nicola Galesi, Barnaby Martin
We investigate the size complexity of proofs in -- an extension of Resolution working on -DNFs instead of clauses -- for families of contradictions given in the {\em un…
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.