問題タブ [np]

CLIQUE 問題 -- グラフ内の最大クリークを見つける問題は NP 完全です。つまりCLIQUEは

a.) NP および b.) 多項式時間で CLIQUE に還元される NP 完全問題 (1 つは 3-SAT) です。

上記の (b) の部分は問題ありません。すべてのリソースで十分に説明されています。パート (a) については、私が知っていることから、次のことが必要です: 特定のソリューション インスタンスが与えられた場合、そのソリューションがこの問題に対する答えであることを多項式時間で検証できることを示す必要があります。したがって、たとえば、特定のグラフとそのサブグラフが与えられた場合、そのサブグラフがそのグラフで最大サイズのクリークであるかどうかを確認できるはずです。

私がこれまでに読んだリソースでは、このパート (a) を「簡単、簡単など」または「指定されたサブグラフがクリークかどうかを O(n^2) 時間で示すことができる」と表現しています。ただし、ここでの検証はクリークであるかどうかだけではなく、グラフの最大のクリークであるかどうかです。これは多項式時間でどのように決定できますか?

ここで何が欠けていますか？

ウィキによると、（N-1）かかります！N都市のツアーを計算します。それを行うためのより良い方法を見つけましたが、それをどれだけ改善したかを計算するための計算を行うことはできません. 私の自宅の PC では、20 都市の地図を 1 時間以内に解くことができました。20！= 2.43290200e+18. これが私がしたことです：

N 個の都市 (名前を付けましょう: City(1)、City(2)、City(3)... City(N)) のルートを braut アルゴリズムで検索する場合、最初に次のテストを実行します: City( 1)、City(2)、City(3)、City(4)... City(N)、そしてしばらくしてから、City(1)、City(3)、City(2)、City(4) )...都市(N). 2番目の計算は不要だと主張しています。City(4) ... City(N) の最短ルートを 1 回だけ計算した場合、それを 2 回目の計算に使用して、どのルートがより適切かを判断できます。

このトリックを使用して、K 都市に対して行っている計算の数を次のように減らすことができます: (N - k) これは、誰が最初の都市になるかを示すことができるオプションの数であり、(N - K - 1) を掛けます。 ! これは、残りの都市を選択するために必要なオプションの数であり、完全な計算を実行するために必要な最初の時間を差し引いたものです。なので(N-K)!となります。そして、k = 3 から k = N - 2 までのすべての K について合計する必要があります。

これは私が行った限りです（それほど遠くありません）...これを計算するのを手伝ってくれることを願っています.

私は問題があります。NP困難な問題だと思いますが、よくわかりません。まず、スペースについて説明します。

次に、イベントがあると仮定して、a,b,c,d,e,fこれらのイベントから生成された 3 つの長さの順序付けられたシーケンスのすべての可能性を検討します。お気に入り、

順序はシーケンスにとって重要であるため、合計 120 の 3 長のシーケンス (6 つのイベントの順列) があります。さらに、これらの 3 つの長さのシーケンスはすべて、0 と 1 の間の独自の値になります。

ここで、長さ 6 のシーケンスを考えてみましょう。

の値は、 のseq3 つの長さのシーケンスをすべて合計して決定できますseq。

からの 3 つの長さのシーケンスはすべて、順序を変更せずにseqから任意の 3 つのイベントを取得することで見つけることができます。seqそれらのいくつかの例;

質問は;

考えられるすべての 6 長のシーケンスの中で最小 (または最大) の値を持つ6 長のシーケンスを見つける必要があります。ご想像のとおり、これは単純な例にすぎません。20 ～ 100 のイベントがある最大のスペースで作業する必要があります。したがって、6 つの長さのシーケンス スペースをすべて生成することは解決策ではありません。

最小 (または最大) を見つけるのは本当に難しいことを知っているので、値が最小 (または最大) に近いシーケンスを見つけることも許容される場合があります。Pythonで実装できるアルゴリズムまたは方法を提案していただければ幸いです。

ありがとう、

私はあなたが検証証明書を与えることができないことを知っています. しかし、私は考えていたのですが、SAT を決定する NDTM に入力を与えてから、答えを逆にできないのはなぜでしょうか? 欠陥はどこにありますか？

FPTAS は 0-1 ナップザックのような弱い NP 問題に適用できることがわかりました。

しかし、ビン パッキングのような強力な NP 問題に同じ原則を適用できないのはなぜですか。同じことについて wiki ページもチェックしましたが、ほとんど理解していませんでした。