１分でNP、NP完全、NP困難の違いを理解する

NP問題

まずはNP問題の定義について説明します。多項式時間＝現実的な時間です。ある判定問題がNPに属するなら

• 問題に対する証拠wが与えられたとき、その証拠wが本当に正しいかどうかを多項式時間で判定できる。

ということになります。証拠があれば現実的な時間で解けるが、証拠がなければ現実的な時間で解けないということです。

例えば、あなたが北海道から鹿児島まで歩いて移動する（NP問題）としましょう。グーグルマップ（証拠）があれば簡単そうですが、なかったら難しそうですね。

帰着

次にNP完全と困難の定義に使う帰着^[1]について説明します。

• 問題Aが問題Bに帰着できる

という関係は

• 問題Bを解く手順があったら問題Aを解ける

ということです。つまり、Aを解く関数をsolve_a、Bを解く関数をsolve_bとすると

def solve_a():
    #なんかする
    answer_b=solve_b()
    #なんかする
    return answer_a 

のような関数が実現でき、その答え(answer_a)が正しいことになります。

NP完全問題、NP困難問題

最後にNP完全と困難を説明します。NP完全問題とは

• 任意のNP問題と同等かそれ以上に難しいNP問題

NP困難問題とは

• 任意のNP問題と同等かそれ以上に難しい問題

のことです。２つの違いは

• NP完全問題はNP問題
• NP困難問題はNP問題でなくてもいい

ということです。正確に定義すると

• 問題$L$がNP困難問題とは、任意の$L'\in NP$に対し$L'$を$L$に現実的な時間で帰着できる。
• 問題$L$がNP完全問題とは、$L\in NP$でありかつ、任意の$L'\in NP$に対し$L'$を$L$に現実的な時間で帰着できる。

ということになります。

まとめ

以下の記事で暗号とNP問題の関係についても説明しています。

https://zenn.dev/senk/articles/cd8b454f14825dcaf7ec

脚注

1. 多対一帰着という特殊ケースも存在する。これはここで述べられているチューリング帰着よりも弱い。