計算の複雑さ
計算の複雑さ (けいさんのふくざつさ) は、計算機のモデルとそのモデルにおける計算に必要な資源によって評価される。
• 領域計算量 • 時間計算量
有名な問題のクラス
• P • NP （NP困難,NP完全） • Co-NP • P • PSPACE • EXPSPACE;-困難 (-hard):問題のクラスCに対して、ある問題PがC困難であるとは、クラスCに属する任意の問題をPに多項式時間還元できるということである。すなわち、問題PはクラスCに属するいかなる問題よりも、同等かそれ以上に難しいということである。
;-完全 (-complete):問題のクラスCに対して、ある問題PがC完全であるとは、PがCに属しかつC困難ということである。すなわち、問題PはクラスCに属する問題の中で、本質的に最も難しい問題であるということである。
