計算量理論

計算量理論は、アルゴリズムが問題を解決するために必要とする時間、メモリ、およびその他のリソースの量によって問題を分類し、効率的に解決可能なものと、解決が困難であると思われるものとの間に明確な境界線を引きます。

Definition

計算量理論は、チューリングマシンなどのモデル上で問題を解決するために必要な、主に実行時間とメモリというリソースによって測定される計算問題の本質的な困難さを研究し、それに応じて問題を計算量クラスに分類します。

Scope

この分野は、P、NP、PSPACEなどの時間計算量クラスと空間計算量クラス、多項式階層、NP完全性理論と多項式時間帰着、中心的なP対NP問題、およびランダム性、相互作用、証明を組み込んだリソース制限モデル、ならびにこれらのクラスを関連付ける階層と困難性の結果を扱います。

Sub-topics

• NP完全性と還元
• ランダム化計算と対話型計算
• P対NP問題
• 時間計算量と空間計算量のクラス

Core questions

• 与えられた問題を解決するには、本質的にどれくらいの時間とメモリが必要ですか？
• どの問題が効率的に解決でき、どの問題がすべての効率的なアルゴリズムに抵抗するように見えますか？
• 問題が計算量クラスの最も困難なメンバーと同じくらい困難であることをどのように示しますか？
• ランダム性、相互作用、または非決定性は、真の計算能力を追加しますか？

Key theories

時間計算量階層定理と空間計算量階層定理

厳密により多くの時間または空間が与えられれば、機械は厳密により多くの問題を解決でき、計算量クラスが真の階層を形成し、一部の問題が他の問題よりも本質的に困難であることを証明します。

NP完全性

クック-レヴィン定理は、他のすべてのNP問題が帰着するNP内の問題を特定するため、それらのいずれか1つに対する単一の効率的なアルゴリズムがあれば、それらすべてを効率的に解決できることになります。

リソース制限モデル

ランダム性、相互作用、または交代性を追加することで、BPP、IP、多項式階層などのクラスが定義され、それらの関係は、追加のリソースが何をもたらし、何をもたらさないかという全体像を明確にします。

Clinical relevance

計算量理論は、どの問題が効率的なアルゴリズムを許容し、どの問題がNP困難であるためヒューリスティクスや近似によって最もよく対処されるべきかを証明することによって、実践を導きます。また、特定の困難な問題の推定される困難性は、計算上実行不可能であると信じられているタスクにセキュリティが依存する現代の暗号技術を支えています。

History

ハートマニスとスターンズは1965年に計算量クラスを定義し、階層定理を証明することによってこの分野を創設しました。クックとレヴィンは1971年頃にNP完全性を導入し、カープは1972年に多くの自然な問題が完全であることを示し、その後の数十年でランダム化、対話型、確率的に検証可能な証明モデルが追加されました。

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Juris Hartmanis

Seminal works

• cook1971
• hartmanisStearns1965
• aroraBarak2009

Frequently asked questions

計算可能性と計算量の違いは何ですか？

計算可能性は、コストを無視して、問題が何らかのアルゴリズムによって解決できるかどうかを問います。計算量は、問題が解決可能であることを前提とし、その解決策が時間とメモリの面でどれほど高価でなければならないかを問い、原理的に解決可能な問題の間でより細かい区別をつけます。

NP完全性が実践においてなぜ重要なのでしょうか？

問題がNP完全であると示された場合、それは何十年もの努力にもかかわらず効率的なアルゴリズムが知られていない他の何千もの問題と結びつけられます。これは、高速な厳密なアルゴリズムを追求することは無駄である可能性が高く、近似、ヒューリスティクス、または特殊ケースの方法が現実的な道であることを示唆しています。