強いNP完全性

計算の複雑さにおいて、強い NP 完全性は、 NP 完全性の特殊なケースである計算問題の特性です。一般的な計算問題には数値パラメータが含まれる場合があります。たとえば、ビンパッキング問題への入力は、特定のサイズのオブジェクトのリストと、オブジェクトを格納するビンのサイズです。これらのオブジェクト サイズとビン サイズは数値パラメータです。

問題が強くNP完全（強い意味でのNP完全）であると言われるのは、その問題の数値パラメータのすべてが入力の長さの多項式で制限されている場合でもNP完全のままである場合です。 ^{[1]強くNP完全な問題が多項式還元される場合、その問題は強く}NP困難であると言われます。特に組み合わせ最適化では、「強くNP困難」という語句は、別の強くNP完全な問題への多項式還元がないことが知られている問題に対してのみ使用されます。

通常、問題の数値パラメータは位置表記法で与えられるため、入力サイズnの問題には、サイズがnの 指数関数となるパラメータが含まれる可能性があります。パラメータが単項表記法で与えられるように問題を再定義すると、パラメータは入力サイズによって制限される必要があります。したがって、強い NP 完全性または NP 困難性は、この問題の単項バージョンの NP 完全性または NP 困難性として定義することもできます。

たとえば、ビンパッキングは強くNP完全ですが、0-1ナップサック問題は弱NP完全です。したがって、オブジェクトとビンのサイズが多項式で制限される整数であるビンパッキングのバージョンはNP完全のままですが、対応するナップサック問題のバージョンは動的計画法によって擬似多項式時間で解決できます。

理論的な観点からは、多項式的に制限された目的関数を持つ任意の強いNP困難な最適化問題は、 P = NPでない限り、完全な多項式時間近似スキーム（またはFPTAS）を持つことができません。^{[2] [3]}しかし、逆は失敗します。たとえば、PがNPに等しくない場合、 2つの制約を持つナップサックは強いNP困難ではありませんが、最適な目的が多項式に制限されている場合でもFPTASはありません。^[4]

NP 完全性の高い問題の中には、平均的には簡単に解決できるものもありますが、実際には難しい例に遭遇する可能性が高くなります。

P≠NPと仮定すると、整数の計算問題では次のことが成り立つ。^[5]

• 問題が弱 NP 困難である場合、その問題には弱多項式時間アルゴリズム(整数の数と最大整数のビット数に関する多項式) はありませんが、擬似多項式時間アルゴリズム (整数の数と最大整数の大きさに関する多項式) は存在する可能性があります。例としては、分割問題があります。弱 NP 困難性と弱多項式時間はどちらも、入力エージェントをバイナリ コーディングでエンコードすることに対応します。

• 問題が強く NP 困難である場合、疑似多項式時間アルゴリズムすら存在しません。また、完全に多項式時間の近似スキームもありません。例としては、3 分割問題があります。強い NP 困難性と疑似多項式時間はどちらも、入力エージェントを単項符号化でエンコードすることに対応します。