誰かが最も簡単な方法で私に説明できます3-SATかVertex Cover? こちらの説明に従っています(4 ページ下部までスクロール)。2 ノード変数ガジェットと 3 ノード節ガジェットの 2 つの「ガジェット」を持つ基本的なセットアップを理解しています。k = variables + 2 clausesまた、すべてのエッジをカバーするために必要なノードの最小数として式を理解しています。私が理解していないのは、この設定が存在する場合k-covering、CNFのブール式が満足できることを証明する方法です。充足可能な式と充足不可能な式の例が役立ちます。また、3-SAT問題が に変換されるとk-covering、どの値(trueまたはfalse) を各変数に割り当てて、ブール式 ? を満たす必要があります。助けてくれてありがとう。
1500 次