Backlinks

• PvsNP問題

  PvsNP問題

  入力長に対してで解けるがクラスP : 正例の証拠(trueであるという一つの証拠)が多項式時間で検証できる を示す 例: 三彩色問題で、塗り分けられるという証拠(=塗り分けられたグラフ)が本当に塗り分けられているのか多項式時間で検証できる (健全性 = falseの検証は、全ての証拠の検証をしないといけない) = 最も"難しい"問題 問題Aが問題Bにさせられる時、Aの難しさ ≦ Bの難しさ (帰着させるときの入力の変換は多項式時間じゃないといけない) NP完全問題同士はお互いに帰着できる NP困難なら必ずしもNPであると言うわけではない = NPかつNP困難である P⊆NPはわかっている = チューリング機械は、局所的にしか変化が起きない #局所性 P=NPだと、全ての問題がでとけちゃう のにも大きな影響 P!=NPだと、影響小さめではあるけどに関わる とかは、が効率的に解けないと言う予想の元に成り立ってる (NPだけどPじゃないっぽいという予想) P!=NPなら、簡単に検証できるけど答え出すのはむずい問題が存在することが証明される の5つの可能世界から、どれが自分たちの世界なのかを知りたい っていうのがこの分野のテーマ? 問題同士の関係を考えて、分類すると言うアプローチが他の分野でも応用できるのかなーと思った #情報科学...

  1/3/2023