SAT-BOOLEN SAT

Question

Je me demandais la complexité des tests SAT avec des variables $ x_i = 0 lor 1 lor 2 DOTS lor n $, les clauses étant de la forme $ x_i = a implique x_j neq b $. Lorsque $ n = 2 $, nous avons du 2SAT, qui a des algorithmes de temps linéaires. En attendant, si $ n> 2 $, alors si nous pouvons presque le convertir en 2SAT en ayant des variables booléennes $ x_ {i, a} $ correspondant à l'instruction $ x_i = a $, Cependant, cela permet $ x_ {i, 1} = x_ {i, 2} = dotes = x_ {i, n} = 0 $, qui partirait $ x_i $ Non attribué.