证明$ 0 $ - $ 1 $ $ MATHSF {ineq} $是$ Mathsf {nl} $ - 完成

Question

我需要证明以下问题$ 0 $ - $ 1 $ $ MATHSF {ineq} $是$ Mathsf {nl} $ - 完成。

给定一组有限的变量$ v $，表格$ x le y $（其中$ x，y in v $）的有限不平等以及表格$ x = a $的有限平等集在 {0,1 } $中的$ x in v $中的$ x in in a in a in {0,1 } $），是否有从$ {0，1 } $分配到满足所有不平等和所有平等性的变量的值？

我如何开始解决证明？

Answer 1

提示：定向可及性是NL完整的。

Answer 2

提示：这是伪装的2sat。