Beweisen Sie, dass $ 0 $-$ 1 $ $ mathsf {iNeq} $ ist $ mathsf {nl} $-vollständig

Question

Ich muss beweisen, dass das folgende Problem $ 0 $-$ $ $ $ Mathsf {Ineq} $ ist $ mathsf {nl} $-vollständig.

Angesichts einer endlichen Variablen $ v $, ein begrenzter Satz von Ungleichheiten des Formulars $ x le y $ (wobei $ x, y in v $) und ein begrenzter Satz von Gleichheiten des Formulars $ x = a $ ( Wo $ x in v $ und $ a in {0,1 } $), gibt es eine Zuordnung von Werten von $ {0, 1 } $ zu den Variablen, die alle Ungleichheiten und Gleichungen erfüllen?

Wie kann ich beginnen, den Beweis zu lösen?

Answer 1

Hinweis: Die gerichtete Erreichbarkeit ist NL-Complete.

Answer 2

Hinweis: Dies ist 2Sat in Verkleidung.