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

公開:2020/10/12
更新:2020/10/21
1 min読了の目安(約1000字TECH技術記事

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問題と同等かそれ以上に難しい問題

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

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

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

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

ということになります。

まとめ

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

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

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