Modular difference logic is hard
  In 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. 
Nikolaj Bj{\o}rner (1), Andreas Blass (2), Yuri Gurevich (1), and   Madan Musuvathi (1)