計算複雑性において、NP完全（またはNP困難）な問題が弱NP完全（または弱NP困難）であるとは、問題の次元とデータの大きさ（これらは整数で与えられるものとする）の多項式実行時間を持つアルゴリズムが存在する場合を指す。データの大きさの2を底とする対数ではなく、多項式実行時間を持つアルゴリズムが存在する場合を指す。このようなアルゴリズムは、技術的には入力サイズの指数関数であるため、多項式とはみなされない。[1]
たとえば、NP 困難なナップザック問題は、ナップザックのサイズとアイテムの数の多項式のステップ数を必要とする動的計画法アルゴリズムで解決できます(すべてのデータが整数にスケーリングされていると仮定)。ただし、オブジェクトとナップザックの入力サイズはその大きさが対数であるため、このアルゴリズムの実行時間は指数時間です。ただし、Garey と Johnson (1979) が指摘したように、「疑似多項式時間アルゴリズムは、'指数関数的に大きい' 数値を含むインスタンスに直面した場合にのみ '指数関数的な動作' を示し、これは私たちが関心のあるアプリケーションではまれである可能性があります。そうであれば、このタイプのアルゴリズムは多項式時間アルゴリズムとほぼ同じように目的にかなう可能性があります。」 弱 NP 完全問題の別の例は、部分集合の合計問題です。
関連用語である「強くNP完全（または単項NP完全）」は、データが単項でエンコードされている場合でも、つまりデータが全体の入力サイズに比べて「小さい」場合でもNP完全のままである問題を指します。[2]
強いNP困難性と弱いNP困難性 vs. 強い多項式時間アルゴリズムと弱い多項式時間アルゴリズム
P≠NPと仮定すると、整数に関する計算問題では次のことが成り立つ。[3]
- 問題が弱NP困難である場合、弱多項式時間アルゴリズム（整数の数と最大整数のビット数に関する多項式）は存在しませんが、擬似多項式時間アルゴリズム（整数の数と最大整数の絶対値に関する多項式）は存在します。例としては、分割問題が挙げられます。弱NP困難性と弱多項式時間はどちらも、入力整数をバイナリ符号化で符号化することに対応します。
- 問題が強NP困難である場合、擬似多項式時間アルゴリズムすら存在しません。また、完全多項式時間近似スキームも存在しません。例としては、3分割問題が挙げられます。強NP困難性と擬似多項式時間はどちらも、入力整数を単項符号化で符号化することに対応しています。
参考文献
- ^ MR Garey、DS Johnson著『コンピュータと扱いにくさ：NP完全性理論へのガイド』WH Freeman、ニューヨーク、1979年。
- ^ L. Hall. 計算複雑性（Wayback Machineに2006年12月7日アーカイブ）ジョンズ・ホプキンス大学。
- ^ Demaine, Erik. 「アルゴリズムの下限値：困難性証明を楽しむ、講義2」。
