Prove that $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete
-
16-10-2019 - |
سؤال
I need to prove that the following problem $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete.
Given a finite set of variables $V$, a finite set of inequalities of the form $x \le y$ (where $x, y \in V$) and a finite set of equalities of the form $x=a$ (where $x \in V$ and $a \in \{0,1\}$), is there an assignment of values from $\{0, 1\}$ to the variables satisfying all the inequalities and all the equalities?
How can I start to resolve the proof?
المحلول
Hint: Directed reachability is NL-complete.
نصائح أخرى
Hint: This is 2SAT in disguise.
لا تنتمي إلى cs.stackexchange