Modular difference logic is hard

Simple item page
dc.creatorBjørner, Nikolaj
dc.creatorBlass, Andreas
dc.creatorGurevich, Yuri
dc.creatorMusuvathi, Madan
dc.date2008-11-06
dc.date.accessioned2026-07-07T10:16:26Z
dc.date.available2026-07-07T10:16:26Z
dc.descriptionIn connection with machine arithmetic, we are interested in systems of constraints of the form x + k \leq y + k'. Over integers, the satisfiability problem for such systems is polynomial time. The problem becomes NP complete if we restrict attention to the residues for a fixed modulus N.
dc.identifierhttps://arxiv.org/abs/0811.0987
dc.identifierhttp://arxiv.org/abs/0811.0987
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/173506
dc.subjectComputational Complexity
dc.titleModular difference logic is hard
dc.typetext

Files

Collections

arXiv