スコット・アーロンソン 著 森弘之 訳「デモクリトスと量子計算」メモ
スコット・アーロンソン 著 森弘之 訳
「デモクリトスと量子計算」メモ
第６章 Ｐ、ＮＰ、その仲間たち
【まとめ】
・Ｐ問題はチューリングマシンで多項式時間に解ける問題のクラス、ＮＰ問題は答えがイエスなら、それを多項式時間内に示せる多項式サイズの証拠が存在するような問題のクラス。
・Ｐ対ＮＰ問題（Ｐ＝ＮＰ or Ｐ≠ＮＰ）は、人類が問うてきた中でもっとも深い問題の一つ。・問題がＮＰ困難であり、ＮＰに含まれるのであれば、それはＮＰ完全と呼ばれ、多くの自然な問題がＮＰ完全で、ＰとＮＰ完全の間には「中間」の問題がなければならない。
