それが強くNP完成であることを意味するものを明確にする

Question

ウィキペディアは、

のように強くNPを定義します。

問題は、その数値パラメータの全てが入力の長さの多項式によって境界に囲まれている場合でも、それがそのように存在する場合には問題があると言われています。

これを意味するのはこれに関係するものです：

3分割の問題を検討しましょう。これは、私たちの数値Paramerは $ \ sum_ {x} x= b $ です。この問題は強くNP-Completeであるため、多項式 $ p（n）$ が存在します。このように $ s $ $ b 、この問題はまだnp-completeです。 （すなわち、 $ |の複雑さ多項式を備えたアルゴリズムを見つける。$ この制限はp= np）

を証明するでしょう）

これは正しい解釈ですか？もしそうであれば、このような多項式の上限を見つけることができます $ p $ 、3分割問題のような有名な問題には？また、間違っていない場合、これは、 $ b $ 、および $ | | $ 、right？

Answer 1

はい、それは正しいです。あなたはおそらく多項式を自分で理解する必要があるでしょう。多項式を見つける方法は、減少を見て、そしてそれからあなたが多項式を推定することができるはずです。

あなたの場合、私は3Dマッチングから3つのパーティションへの削減があると思います。3Dマッチングのインスタンスを考えると、減少は、3Dマッチングインスタンスを解くために使用できる3Partitionのインスタンスを明示的に構築します。そのため、セットのサイズの関数として、3Partitionインスタンスのパラメータが大きくなる可能性があるかを分析し、それが多項式 $ p $ を伝えます。あなたは探しています。