CLIQUE 問題 -- グラフ内の最大クリークを見つける問題は NP 完全です。つまりCLIQUEは
a.) NP および b.) 多項式時間で CLIQUE に還元される NP 完全問題 (1 つは 3-SAT) です。
上記の (b) の部分は問題ありません。すべてのリソースで十分に説明されています。パート (a) については、私が知っていることから、次のことが必要です: 特定のソリューション インスタンスが与えられた場合、そのソリューションがこの問題に対する答えであることを多項式時間で検証できることを示す必要があります。したがって、たとえば、特定のグラフとそのサブグラフが与えられた場合、そのサブグラフがそのグラフで最大サイズのクリークであるかどうかを確認できるはずです。
私がこれまでに読んだリソースでは、このパート (a) を「簡単、簡単など」または「指定されたサブグラフがクリークかどうかを O(n^2) 時間で示すことができる」と表現しています。ただし、ここでの検証はクリークであるかどうかだけではなく、グラフの最大のクリークであるかどうかです。これは多項式時間でどのように決定できますか?
ここで何が欠けていますか？