tardos のアルゴリズム設計書から NP 完全性について読んでいます。サブセット和が NP 完全であることを証明するセクションでは、次のように書かれてい
ます。サブセット和用に開発されたアルゴリズムの実行時間は O(nW) です。それぞれが 100 ビット長の 100 個の数値のインスタンスが与えられた場合、入力は 100 * 100 = 10000 桁にすぎませんが、W はおよそ 2^100 です。
この主張が理解できません。なぜ W 2^100 なのですか? この問題に対する base の影響は何ですか? つまり、それを別の base x に変更すると、W は x^100 になりますか? 単項ベースに変更するとどうなるでしょうか?
ありがとう。
1 に答える
0
これを理解するには、問題セットの数値のサイズが大きくなるにつれて、アルゴリズムの実行時間がどのように変化するかを考える必要があります。あなたの教科書には、サブセットの合計に対する通常の動的計画法の攻撃が記述されていると思います。そのアルゴリズムの実行時間は、問題セットの幅に比例して増加します。(問題のセットの幅は、セット内の正の数の合計から負の数の合計を引いたものです。) この幅は、セット内の数値のサイズを大きくすると指数関数的に大きくなります。 たとえば、100 ビットの数値の代わりに 101 ビットの数値を使用すると、問題セットの幅が2 倍になります。. 102 ビットの数値に移行すると、問題セットの幅が再び 2 倍になります。また、アルゴリズムの実行時間は問題セットの幅に比例して増加するため、実行時間も毎回 2 倍になります。この 2 倍は、入力サイズが直線的に増加するため、実行時に指数関数的に増加するため、これは多項式時間アルゴリズムではありません。
数値が 1 を超える別の基数で書かれている場合は、その基数で問題の幅が指数関数的に増加することがわかります。たとえば、底が 10 の場合、別の桁を追加すると、問題の幅が 10 倍になります。単項に切り替えると、問題セットのサイズの指数関数的な増加は失われますが、その代わりに、特定の問題の入力サイズが基数 > 1 の場合よりも指数関数的に大きくなるため、何も得られません。
于 2012-01-04T00:38:07.163 に答える