سؤال

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.

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top