PvsNP問題

Last updated Unknown Edit Source

入力長に対して多項式時間で解ける判定問題

NP: 正例の証拠(trueであるという一つの証拠)が多項式時間で検証できる判定問題

• 完全性を示す
• 例: 三彩色問題で、塗り分けられるという証拠(=塗り分けられたグラフ)が本当に塗り分けられているのか多項式時間で検証できる
• (健全性 = falseの検証は、全ての証拠の検証をしないといけない)

NP困難 = 最も"難しい"問題

• 問題Aが問題Bに帰着させられる時、Aの難しさ ≦ Bの難しさ
  • (帰着させるときの入力の変換は多項式時間じゃないといけない)
• NP完全問題同士はお互いに帰着できる
• NP困難なら必ずしもNPであると言うわけではない

NP完全 = NPかつNP困難である

P⊆NPはわかっている

• アルゴリズム = チューリングマシン

  チューリングマシン

  ...

  1/3/2023

  • チューリング機械は、局所的にしか変化が起きない #局所性

• P=NPだと、全てのNP完全問題が多項式時間でとけちゃう

  • 数学の証明問題にも大きな影響

• P!=NPだと、影響小さめではあるけど暗号に関わる

  • RSA暗号とかは、素因数分解が効率的に解けないと言う予想の元に成り立ってる (NPだけどPじゃないっぽいという予想)
  • P!=NPなら、簡単に検証できるけど答え出すのはむずい問題が存在することが証明される

• impagliazzoの5つの可能世界から、どれが自分たちの世界なのかを知りたい

  • っていうのがこの分野のテーマ?

• 問題同士の関係を考えて、分類すると言うアプローチが他の分野でも応用できるのかなーと思った #情報科学