Dimostrare che $ 0 $ - $ 1 $ $ \ {mathsf Ineq} $ è $ \ mathsf {NL} $ - completo

Question

ho bisogno di dimostrare che il seguente problema $ 0 $ - $ 1 $ $ \ {mathsf Ineq} $ è $ \ mathsf {NL} $ -. Completo

Dato un insieme finito di variabili $ V $, un insieme finito di disuguaglianze della forma $ x \ le y $ (dove $ x, y \ in V $) e un insieme finito di uguaglianze della forma $ x = un $ (dove $ x \ in V $ e $ a \ in \ {0,1 \} $), esiste un'assegnazione di valori di $ \ {0, 1 \} $ alle variabili che soddisfino tutte le disuguaglianze e tutti le uguaglianze?

Come posso iniziare a risolvere la prova?

Answer 1

Hint: Directed reachability is NL-complete.

Answer 2

Hint: This is 2SAT in disguise.