Demuestre que $ 0 $-$ 1 $ $ mathsf {ineq} $ es $ mathsf {nl} $-completo

Question

Necesito demostrar que el siguiente problema $ 0 $-$ 1 $ $ mathsf {ineq} $ es $ mathsf {nl} $-completo.

Dado un conjunto finito de variables $ V $, un conjunto finito de desigualdades de la forma $ x le y $ (donde $ x, y en v $) y un conjunto finito de igualdades de la forma $ x = a $ ( donde $ x en v $ y $ a in {0,1 } $), ¿hay una tarea de valores de $ {0, 1 } $ a las variables que satisfacen todas las desigualdades y todas las igualdades?

¿Cómo puedo comenzar a resolver la prueba?

Answer 1

Sugerencia: la accesibilidad dirigida es NL complete.

Answer 2

Sugerencia: este es 2SAT disfrazado.