ハーフクリーク-NP完全な問題

Question

気付かないうちに始めましょう これは宿題の問題です。アドバイスと関連する観察のみを提供してください、直接の回答はありません. 。とはいえ、私が見ている問題は次のとおりです。

let half-clique = {$ langle g rangle $ | $ g $は、少なくとも$ n/2 $ノードを備えた完全なサブグラフを持つ無向グラフで、nは$ g $}のノードの数です。ハーフクリークがNP完全であることを示します。

また、私は次のことを知っています：

• この問題に関してはa クリーク, 、入力グラフの無向サブグラフとして定義され、2つのノードごとにエッジによって接続されます。 a $ k $ -Clique $ k $ノードを含むクリークです。
• 私たちの教科書によると、マイケル・シップサーの」計算理論の紹介"、pg 268、問題clique = {$ langle g、k rangle $ | $ g $は、$ k $ -Clique}を持つ無向グラフです。
• さらに、同じソース（Pg 283）によると、クリークはNPコンプレテ（したがって明らかにNPでも）にあることに注意しています。

私はここに答えの核を持っていると思いますが、私は使用できます それに何が悪いのか、または答えに関連する可能性のある関連するポイントのいくつかの兆候. 。これは私がこれまでに持っている一般的な考えです、

わかりました、最初に証明書は単に$ text {size} geq n/2 $の半qliqueになることに注意してください。今、私がする必要があるのは、クリーク（NP Completeであることがわかっている）から半分のクリークまでの多項式時間削減である検証剤を作成することです。私の考えは、これは、ハーフクリークのための追加の制約を備えたクリークのために本のチューリングマシン検証剤を実行するチューリングマシンを作成することによって行われるということです。

これは私には正しいように聞こえますが、私はまだこのテーマで自分自身を本当に信用していません。もう一度、私は皆に思い出させたいと思います これは宿題の問題です 質問に答えないようにしてください。これに及ぶガイダンスは、大歓迎です！

Answer 1

あなたの説明とコメントから判断すると、NPの完全性を証明するために削減をどのように使用できるかについての正確な説明によって、あなたは最善を尽くされるかもしれません：

問題は、NPがNPであり、NPハードです。これは、NP不完全性の証明には2つの部分があることを意味します。問題がNPにあることの証明と、それがNPハードであることの証明です。

最初の部分では、適切な証明書を使用して、Yes-Instancesを多項式時間に検証できることを示す必要があります。あるいは、問題を非決定的なチューリングマシンによって多項式時間に解決できることを示すことができますが、これは通常、間違いが簡単に行われるためには行われません。

あなたの場合、これは、$ n/2 $ cliqueを持つすべてのグラフについて、実際にそのようなクリークがあるという証拠を見つけることができることを証明することになります。確かにそのようなクリークがある時間。

2番目の部分では、問題がNPハードであることを示す必要があります。これは、あなたの問題が少なくとも他のNPハードの問題と同じくらい難しいことを証明することによって示されるほぼすべての場合です。ハーフクリークがクリークと同じくらい困難である場合、それもNPハードでなければなりません。

削減を証明することにより、これを行います から クリーク、 に ハーフクリーク。問題を「軽減」し、「簡単に」します。あなたは「クリークを解くのは難しいですが、私はあなたがクリークを解決するために半分を解決するだけであることが必要であることを証明しました」。 （多くの人々、専門家でさえ、時々これを間違った方法で言う:)）

削減にはさまざまな種類があります。最も一般的に使用される削減は、この場合、サイズが多項式時間で最も多項式的に大きいハーフクリークのインスタンスにインスタンスをマッピングするものです。これは、ハーフクリークを解決できれば、アルゴリズムと削減をチェーンすることでクリークを解決できることを意味します。

言い換えれば、半分のクリークを解決できれば、クリークを解決できることを示さなければなりません。これを行うことで、Cliqueのすべてのインスタンスについて、Half-Qliqueのインスタンスが「はい」インスタンスである場合、クリークのインスタンスが「はい」インスタンスになるように、ハーフクリークのインスタンスを設計できることを示します。

したがって、証明は次のように始まります。グラフ$ g =（v、e）$を与えられた場合、$ g $が$ k $ -clique iff $を含むようにグラフ$ h =（v '、e'）$を作成できます。 H $には$ n/2 $ -Cliqueが含まれています。この部分をあなたに任せます（これは創造性を必要とする部分であり、特定の問題についての部分です）。

Answer 2

あなたは少し迷っているようです。ハーフクリーク$ ge $ cliqueを示したいと思います。つまり、「はい」の入力を入力して入力し、出力の半分のインスタンスを「はい」と出力するポリタイムアルゴリズムを探していることを意味します。はい "esと" no "入力は「いいえ」にマップします。

したがって、基本的に、タスクはグラフ$ g $と数$ k $を取得し、新しいグラフ$ h $（および数値なし）を出力することです。 G $にはサイズ$ k $のクリークがあります。

以下のネタバレには、この削減の実行方法に関するヒントが含まれています。

（何らかの形で）適切なサイズのクリークを$ g $に添付することにより、$ h $を作成して、何にも接続されていないいくつかの頂点を作成してみてください。

Answer 3

頂点カバーの問題から減らすことができます。指定されたグラフの補数グラフにn/2ノード未満の頂点カバーがある場合、このグラフにはn/2ノード以上のクリークがあり、それは半分のクリークになります。頂点カバーの問題を解決することは難しいと述べてください。