[解決済み] NPとco-NPの違いは何ですか？

質問事項

完全な対応というのは NP - completeはNP問題で最も難しく、co-NP-completeはco-NP問題で最も難しいという意味ですが、この2つの違いは何でしょうか？教科書には「YESとNOが逆」と書いてありましたが、私にはあまりピンと来ません。

解き方は？

ある問題の難しさを証明したいとき、その問題を決定問題（decision problem）と呼ばれる、「はい／いいえ」で答えるタイプの問題に変換する必要があります。例えば、集合カバーの問題では、次のような問題があります。 X個の部分集合だけですべての要素をカバーできますか？ ここで、Xはある任意の数である。あなたはX個の部分集合を提供し、私は多項式時間ですべての要素がカバーされているかどうかをチェックします。もし、決定問題に対して効率的に "yes"と答えることができれば、Xを最小化できるので、集合被覆問題全体を効率的に解くことができます（それによって、P=NPを証明することができるのです）。

Co-*（Co-NP、Co-NP-complete）は、補完された決定問題に対して"no"と答えることに焦点を当てたものです。例えば、Set Cover の補集合決定問題は ".となる。 X個の部分集合のすべての組み合わせについて、すべての要素をカバーすることは不可能ですか？ この質問に対して、「いいえ」と答えるには、反例を示す必要があります。

要約すると、NPはある決定問題に対する答えがquot;yes"であることに関係しています。Co-NPは、同じ、しかし補完された決定問題に対する"no"の答えに関係します。