計算量理論

Last updated Unknown Edit Source

• 理論計算機科学

  理論計算機科学

  #情報科学 のうち、の一分野 速さに興味ある人と、正しさに興味がある人とがいる 速さ: とか、とか 正しさ: とか、とか 、、とか 多め #離散 との世界をはっきり重視 #イデア...

  1/3/2023

  のうち、ある問題が効率的に計算でき「ない」ことを追求するもの

• PvsNP問題

  PvsNP問題

  入力長に対してで解けるがクラスP : 正例の証拠(trueであるという一つの証拠)が多項式時間で検証できる を示す 例: 三彩色問題で、塗り分けられるという証拠(=塗り分けられたグラフ)が本当に塗り分けられているのか多項式時間で検証できる (健全性 = falseの検証は、全ての証拠の検証をしないといけない) = 最も"難しい"問題 問題Aが問題Bにさせられる時、Aの難しさ ≦ Bの難しさ (帰着させるときの入力の変換は多項式時間じゃないといけない) NP完全問題同士はお互いに帰着できる NP困難なら必ずしもNPであると言うわけではない = NPかつNP困難である P⊆NPはわかっている = ...

  1/3/2023

  #情報科学