ここから始めましょう: すべてのNP 問題はSAT (ブール充足可能性問題)に還元できると言われています。Circuit SATに対してより正確に言うと、NP のようなすべての意思決定問題は最終的にYesまたはNoの答えになるはずです。
しかし、ランダム NP の問題がある場合、テストするブール回路を作成する方法、入力をグループ化する方法、それらの入力を接続するゲート(AND、NOT、OR など) の種類について説明します。したがって、基本的に、私の質問は、 TRUE または FALSEの答えを与えるブール回路を設計する方法です。
最後に、その答えが何を意味するか。この NP 問題は多項式時間で解くことができ、FALSE はできないため、TRUE は理解できますか?
私の質問を説明する論理的な間違いを犯したとしても、本当にとんでもないことをしないでください:)あなたがそれを理解してくれることを願っています.
興奮して答えを待っています。