弱いNP完全性

計算複雑性において、NP完全（またはNP困難）な問題が弱NP完全（または弱NP困難）であるとは、問題に対するアルゴリズムの実行時間が、問題の次元と関係するデータの大きさ（これらが整数として与えられる場合）の多項式であり、大きさの2を底とする対数ではない場合である。このようなアルゴリズムは技術的には入力サイズの指数関数であるため、多項式とは見なされない。^[1]

たとえば、NP 困難なナップザック問題は、ナップザックのサイズとアイテムの数の多項式のステップ数を必要とする動的計画法アルゴリズムによって解くことができます(すべてのデータが整数にスケーリングされていると仮定)。ただし、オブジェクトとナップザックの入力サイズは対数であるため、このアルゴリズムの実行時間は指数時間です。ただし、Garey と Johnson (1979) が指摘したように、「疑似多項式時間アルゴリズムは、'指数関数的な動作' を示すのは、'指数関数的に大きい' 数値を含むインスタンスに直面したときのみであり、これは、私たちが関心のあるアプリケーションではまれである可能性があります。そうであれば、このタイプのアルゴリズムは、多項式時間アルゴリズムとほぼ同じように目的を果たす可能性があります。」 弱 NP 完全問題の別の例は、部分集合の合計問題です。

関連用語である「強くNP完全（または単項NP完全）」は、データが単項でエンコードされている場合でも、つまりデータが全体の入力サイズに比べて「小さい」場合でもNP完全のままである問題を指します。^[2]

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

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

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