計算複雑性理論

空間計算量に関するサヴィッチの定理の証明を説明します。 後編の今回は、STCON問題を使ってNTMとDTMを結びつけます。

空間計算量に関するサヴィッチの定理の証明を説明します。 前編の今回は、証明に必要なSTCON問題の空間計算量を解説します。

ビジービーバー関数について、ほかの記事を読んだだけではわかりづらいところを補足説明します。

計算理論において、「還元」という言葉は多く登場しますが、還元にも定義の異なるものが複数存在することをご存じでしょうか。 今回は代表的な２つである多対一還元とチューリング還元を説明します。

複雑性クラスは時間だけのものではありません。 問題を解くうえで同じく重要な空間や領域についての話。 PSPACE, NPSPACE, L, NLなどについて説明しました。

co-NPという複雑性クラスを知っていますか。 とんでもない魔境です。

充足可能性問題(SAT)がNP完全問題であることを示す定理「クックの定理（Cook-Levin theorem）」について、英語版Wikipediaの記事をもとに、嚙み砕いて説明しました。 今回は実際の証明を行った。 難しい。

充足可能性問題(SAT)がNP完全問題であることを示す定理「クックの定理（Cook-Levin theorem）」について、英語版Wikipediaの記事をもとに、嚙み砕いて説明しました。 今回は証明のアウトラインだけ。 難しい。

P, NP, NP完全, NP困難など、計算複雑性理論の複雑性クラスについて、自分でわかっていなかったところをまとめました。