$ 0 $ -1 $ $ $ $ mathsf {ineq} $が$ mathsf {nl} $ - 完了であることを証明します

Question

次の問題が$ 0 $ 0 $ 1 $ $ $ mathsf {ineq} $であることを証明する必要があります。

変数の有限セット$ v $、フォーム$ x le y $（ここで$ x、y in v $）の有限の不等式、およびフォーム$ x = a $（ここで、v $および$ a in {0,1 } $）の$ x は、$ {0、1 } $からすべての不平等とすべての等式を満たす変数への値の割り当てはありますか？

どうすれば証明を解決し始めることができますか？

Answer 1

ヒント：指示された到達可能性はNLコンプリートです。

Answer 2

ヒント：これは変装した2SATです。