組み合わせ最適化問題が与えられたとしましょうA.問題がクリーク問題であるとWLOGを仮定しましょう。
クリークがNP完全である場合、クリークの決定バージョンがNP完全であることをどのように示すことができますか。ここで、決定バージョンはもちろん次の問題Bです。kに等しいサイズのクリークはありますか？
私は直感を念頭に置いていると思いますが、それが証拠として十分であるかどうかはわかりません。
ステップI：
サイズkの頂点Cのセットが与えられた場合、サイズkのクリークがあることを多項式時間で確認できます（Bの答えがyesである、つまりサイズkのクリークが存在すると仮定します）。したがって、BはNPにあります。
ステップII：AをBに減らします。
-Aは最大サイズのクリークを要求するので、問題を細かく分割できます。B1：サイズ1のクリークはありますか？、...、BN：サイズNのクリークはありますか？
-Aが可解である場合、たとえばサイズk *のクリークがある場合、すべてのBk、k = 1、...、Nは、kをk*と比較することで簡単に答えることができます。
-すべてのBksが解ける場合、最大クリークサイズはどれくらいかわかります。
多項式時間ですが、これが削減であるかどうかは本当にわかりません。1つの問題が多くの問題に分解されているためかもしれません。また、上記の「すべて」という言葉を使うべきかどうかもわかりません。
助けてくれてありがとう！:)