Montrer que $ 0 $ - $ 1 $ $ \ mathsf {Ineq} $ est $ \ mathsf {NL} $ - complète

Question

Je dois prouver que le problème suivant $ 0 $ - $ 1 $ $ \ mathsf {Ineq} $ est $ \ mathsf {NL} $ -. Complet

Etant donné un ensemble fini de variables $ V $, un ensemble fini d'inégalités de la forme $ x \ le y $ (où $ x, y \ in V $) et un ensemble fini d'égalités de la forme $ x = un $ (où $ x \ in V $ et $ a \ in \ {0,1 \} $), est-il une affectation de valeurs de $ \ {0, 1 \} $ aux variables satisfaisant toutes les inégalités et toutes les les égalités?

Comment puis-je commencer à résoudre la preuve?

Answer 1

Astuce:. Directed est joignabilité NL-complet

Answer 2

Astuce:. Ceci est 2SAT déguisé