algorithm - NPとco-NPの違いは何ですか

Question

それらの完全な対応物は、NP - 完全が NP 問題で最も難しく、co-NP-complete が co-NP 問題で最も難しいことを意味することを知っていますが、2 つの違いは何ですか? 教科書に「はい・いいえが逆」と書いてありましたが、あまり手がかりがありません。

Answer 1

問題の難しさを証明したいときは、それを「決定問題」と呼ばれるもの、つまり「はい/いいえ」で答えるタイプの問題に変える必要があります。たとえば、セット カバーでは、「X サブセットのみを使用してすべての要素をカバーできますか?」と尋ねる場合があります。ここで、X は任意の数値です。この問題の解決策は簡単に検証できるため、この問題が NP に存在することを示すことができます。あなたは X サブセットを提供し、すべての要素が多項式時間でカバーされているかどうかを確認します。決定問題に効率的に「はい」と答えることができれば、X を最小化し、セット カバー問題全体を効率的に解くことができます (したがって、P=NP が証明されます)。

Co-* (Co-NP、Co-NP-complete) は、補完決定問題に対して「いいえ」と答えることに重点を置いています。たとえば、セット カバーの補足決定問題は、「X 個の部分集合のすべての組み合わせについて、すべての要素をカバーすることは不可能か?」となります。この質問に「いいえ」と答えるには、反例を示す必要があります。

要約すると、NP は、何らかの決定問題に対する「はい」の答えに関心があります。Co-NP は、同じであるが補足された決定問題に対する「いいえ」の答えに関心があります。

Answer 2

NPは、適切な証明書が与えられた場合に「はい」のインスタンスを検証できる多項式時間アルゴリズムがある決定問題のクラスです。

CoNPは、適切な証明書が与えられた場合に「いいえ」のインスタンスを検証できる多項式時間アルゴリズムがある決定問題のクラスです。

coNP が NP と異なるかどうかはわかりません。

coNP の問題には NP の問題があり、その逆もあります。たとえば、SAT の問題は、「この数式を True に評価するブール代入は存在しますか?」と尋ねます。coNP にある補数問題は、「すべてのブール代入は、この数式を False に評価するか?」と尋ねます。