|
|
| 1行目: |
1行目: |
| − | '''計算複雑性理論'''（けいさんふくざつせいりろん、{{lang|en|computational complexity theory}}）とは、[[計算機科学]]における[[計算理論]]の一分野であり、[[アルゴリズム]]の[[スケーラビリティ]]や、特定の計算問題の解法の[[複雑性]]（計算問題の困難さ）などを数学的に扱う。'''計算量理論'''、'''計算の複雑さの理論'''、'''計算複雑度の理論'''ともいう。
| + | __NOINDEX__ |
| − | | + | {{テンプレート:20180815sk}} |
| − | {{注|「計算量」と「計算複雑性」はともに {{lang|en|computational complexity}} に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。}}
| |
| − | | |
| − | == 概要 ==
| |
| − | 計算複雑性理論は[[計算可能関数]]の計算の複雑さを扱う。計算理論のもう一つの重要な分野である[[計算可能性理論]]では問題の解法があるかどうかだけを扱い、その複雑さや必要とする計算資源量は問わない点が異なる。
| |
| − | | |
| − | 具体的には、計算複雑性理論は「あるアルゴリズムへの入力データの長さを増やしたとき、実行時間や必要な記憶量はどのように増えるか？」という問いに答える。これは、[[計算機]]の実際的な限界を与えるものであり、この理論は産業や社会にとって重要な意味を持つ。なぜならば、計算機の性能は向上しているが、解析すべき情報も増加しているため、アルゴリズムが入力データ長の増大にうまく対応できるか否かで、計算機が現実的な問題を解決するのに役に立つか否かが決まるからである。
| |
| − | | |
| − | 計算複雑性理論では、計算問題やそれを解くアルゴリズムを、NPやPといった複雑性クラスに分類する。個々の計算問題を少ない計算資源で解くアルゴリズムを発見することはもちろん計算機科学の重要な課題だが、複雑性理論ではこれにとどまらず、計算問題が何らかの複雑性クラスに属すること、あるいは属しないことを証明したり、クラス間の階層構造を解明することも目標とする。
| |
| − | | |
| − | 計算量 t<sub>C</sub> をもつ複雑性クラス C に 或る計算問題 X が属する とは、あるアルゴリズム A が存在して、問題 X が A により t<sub>C</sub>以下で解決されることを意味し、問題 X の複雑性の上界を与える。そして、よりよい上界を求めることは、問題 X をより少ない計算資源で解くアルゴリズムを発見する(あるいはその存在を示す)ことに他ならず、産業界において有意義である。また、ある計算問題 X が、ある複雑性クラス C に属しないとは、問題 X は、いかなるアルゴリズムをもってしても、計算量 t<sub>C</sub> 以下では解決できないことを意味し、問題 X の複雑性の下界を与える。計算問題の下界を示すことは、理論的意義を有するだけではなくて、[[暗号理論]]においては、ある暗号方式が計算量的に解読不能であることを示すことを意味し、実際的な価値がある。
| |
| − | | |
| − | 現在の計算複雑性理論の最も重要な課題は、[[P≠NP予想]]の証明である。この予想は提起された当初それほど重要とは見なされなかったが、産業において重要な[[オペレーションズリサーチ]]の問題の多くが[[NP]]の部分クラスに属する[[NP完全問題]]であることが明らかになるにつれて重要性を増してきた。NP完全問題は、解法が正しいかどうかは簡単に確かめられるが、正確な解を探す方法はスケーラブルではない問題である。NPクラスがPクラスより範囲が広いことが確定すると、それらの問題にはスケーラブルな解が存在しないことが確定する。このため、P≠NP予想の証明は重要とされているのである。
| |
| − | | |
| − | == 計算問題と計算量・複雑性 ==
| |
| − | 計算複雑性理論で扱う'''問題'''とは、ある一連の問いの集合があり、各問いは有限長の[[文字列]]で表され、与えられた問いに対して解を求めて出力する計算問題である。例えば、[[素因数分解|''FACTORIZE'']]問題とは「[[二進記数法|二進数]]で書かれた1つの整数について、その[[素数|素因数]]を全部求めて返す」という問題である。問題に属する個別の問いを'''インスタンス'''と呼ぶ。例えば、「15 の素因数を求めよ」は ''FACTORIZE'' 問題のインスタンスである。
| |
| − | | |
| − | [[アルゴリズム]]の'''計算量'''（けいさんりょう）とは、[[計算機]]がそのアルゴリズムの実行に要する計算資源の量をいい、アルゴリズムの[[スケーラビリティ]]を示す。形式的には計算機を[[チューリング機械]]や[[即時呼出機械]]（{{lang|en|random access machine}}）などの[[計算模型|計算モデル]]として定式化したうえで、アルゴリズムの使用する資源の量を入力データ長などに対する[[関数 (数学)|関数]]として表す。計算モデルの瑣末な詳細に影響を受けないよう、計算量はその漸近的な挙動のみに注目し、定数倍を無視する[[ランダウの記号|O記法]]で書き表すことが多い。計算モデルとしては、[[チューリング機械]]や[[論理回路]]などがある。計算資源の量としては、チューリング機械における'''時間計算量'''（動作ステップ数）や'''空間計算量'''（テープ長）、また論理回路における素子数や深さなどがある。
| |
| − | | |
| − | * '''時間計算量'''は、あるアルゴリズムを使ったときに問題のインスタンスを解くのに要するステップ数を意味し、入力データの長さ（ビット数などで表現できる）の関数として表される。シンプルな例として、ある問題に対する解法が ''n''ビットの入力に対して、ある計算モデルで ''n''<sup>2</sup> ステップで動作する場合、時間計算量は ''n''<sup>2</sup> であるが、他のほとんどの計算モデルでも、時間計算量は漸近的には定数倍の違いしかなく、[[ランダウの記号|O記法]]を使えば計算モデルによらず問題の時間計算量をO(''n''<sup>2</sup>) と表せる。計算を芝生を刈る作業にたとえれば、その時間計算量は線型であり、芝生の面積が2倍になれば時間も2倍かかる。この面積が2倍になれば時間も2倍になるという関係は、芝刈機の速度には関係しない。しかし、辞書を[[二分探索]]する場合の時間計算量は対数時間であり、辞書の厚さが2倍になっても、二分探索のステップが1増加するだけである。
| |
| − | * '''空間計算量'''は、同様の概念であり、アルゴリズムが必要とする記憶容量を意味する。例えば、紙とペンを使って計算を行う際に要する紙の枚数に相当する。空間計算量にも[[ランダウの記号|O記法]]が使われる。
| |
| − | | |
| − | 計算モデルによっては、これらとは異なる計算量が使われることもあり、例えば'''[[回路計算量]]'''がある。これは問題の解法を[[ブール論理]]による[[論理回路]]ゲートに置き換え、その回路の規模で計算量を現すものである。これは[[集積回路]]の設計などで利用される。
| |
| − | | |
| − | 計算問題の'''複雑性'''（または計算量）とは、それがどの計算モデルにおいて、どれほどの計算量のアルゴリズムによって解けるかで測られる。直感的には、問題の計算量は、最も効率のよいアルゴリズムを使ったときに問題のインスタンスを解くのに要する計算量だと考えるのが自然である。しかし、最良のアルゴリズムであることを示すのは通常困難で、多くの場合、O記法を用いて「ある時間以下で計算できる」ことを示すことになる。そのため、複雑性クラスを導入し、クラス間の相互関係を示すことで、計算問題の複雑性を明らかにする。
| |
| − | | |
| − | == 決定問題 ==
| |
| − | 計算複雑性理論で扱う計算問題の多くは[[決定問題]]である。決定問題とは、答えが「はい」か「いいえ」になる問題を指す。
| |
| − | | |
| − | 決定問題を主に扱うのは、任意の計算問題を何らかの決定問題に[[還元 (計算複雑性理論)|還元]]することが常に可能だからである。例えば、''HAS-FACTOR'' を与えられた整数 ''n'' と ''k''（どちらも二進数で与えるとする）について、''n'' が ''k'' より小さい素因数をもつかどうかに答える決定問題とする。すると、計算問題 ''FACTORIZE''（素因数分解）の解法は、''HAS-FACTOR'' を使って実現でき、その際に追加の資源はそれほど要しない。具体的には ''k'' について[[二分探索]]を行い、''n'' の最小素因数を探索し、その値で ''n'' を割る。そして、商について再び同じ作業を繰り返していけばよい。このことは、''HAS-FACTOR'' の解法をある計算資源量で実現できるか否かが分れば、''FACTORIZE'' の解法についても分るということを意味する。
| |
| − | | |
| − | 計算複雑性理論では、答えが「はい」かどうかを確認する問題と、答えが「いいえ」かどうかを確認する問題を区別する。「はい」と「いいえ」を逆転させた問題は、元の問題の[[補問題]]と呼ばれる。
| |
| − | | |
| − | 例えば、決定問題 ''IS-PRIME''（[[素数判定|素数判定問題]]）は、入力が[[素数]]の場合に「はい」、そうでなければ「いいえ」を返す。一方、問題 ''IS-COMPOSITE'' は与えられた整数が素数で'''ない'''（すなわち[[合成数]]である）ことを決定する。''IS-PRIME'' が「はい」を返すなら、''IS-COMPOSITE'' は「いいえ」を返す。逆も成り立つ。したがって ''IS-COMPOSITE'' は ''IS-PRIME'' の補問題であり、同様に ''IS-PRIME'' は ''IS-COMPOSITE'' の補問題である。
| |
| − | | |
| − | ある問題の解を求める計算量とその補問題の解を求める計算量は同じであるが、問題のあるインスタンスについて「はい」となる証拠を与えられて、その証拠が正しいかを判定する計算量は同じとは限らない。例えば、''IS-COMPOSITE''問題で、ある整数について、証拠として素因子を一つ与えられれば、除算を行うことで検算することができる。しかし、''IS-PRIME''問題では、どのような証拠を与えればよいかは、しばらくの間、自明ではなかった。補問題を区別することは、後述する複雑性クラス[[NP]]と[[co-NP]]などで重要となる。
| |
| − | | |
| − | 計算複雑性理論の重要な成果の1つとして、ある難しい問題があったとき（それがいかに大量の時間資源や空間資源を要したとしても）、それよりさらに難しい問題が必ず存在するという事実がある。時間計算量については{{仮リンク|時間階層定理|en|Time hierarchy theorem}}によってこれが証明されている。同様に{{仮リンク|領域階層定理|en|Space hierarchy theorem}}も導かれる。
| |
| − | | |
| − | == 計算資源 ==
| |
| − | 計算複雑性理論は計算問題の難しさを様々な[[計算資源]]の観点で分析する。時間、空間、無作為性、反復性、その他のより直観的でない尺度などで必要とする計算資源量によって、同じ問題を説明する。[[複雑性クラス]]はある特定の計算資源をある特定の量つかって解くことができる全計算問題の集合である。
| |
| − | | |
| − | 最も研究が進んでいる計算資源は'''[[決定性時間]]'''(DTIME) と'''[[決定性空間]]'''(DSPACE) である。これらの資源はそれぞれ、決定性のある計算機（例えば実在する普通の計算機）で問題を解くのに必要な「計算時間（演算回数）」と「記憶装置」の量に対応している。これらの資源の使用量を求めることは実用的な意味もあり、研究が進んでいるのである。
| |
| − | | |
| − | いくつかの計算問題は非現実的な量の資源を想定すれば、より容易に解析可能である。例えば、[[非決定性チューリング機械]]は、分岐して様々な可能性を同時にチェックできるという計算モデルである。したがって、非決定性チューリング機械はアルゴリズムを使って具体的に計算する作業とは全く関係ないが、その分岐によって分析したい計算モデルの大部分を捉える。このため[[非決定性時間]]は計算問題を分析するにあたって非常に重要な資源である。
| |
| − | | |
| − | 計算複雑性理論では他にもいろいろな計算資源を考慮する。技術的には、[[複雑性尺度]]として計算資源量が扱われ、これに関しては[[ブラムの公理]]で非常に一般的な定義が与えられている。
| |
| − | | |
| − | == 複雑性クラス ==
| |
| − | ある量の計算資源を使って解くことができるすべての計算問題の集合を[[複雑性クラス]]という。
| |
| − | | |
| − | 複雑性クラス [[P (計算複雑性理論)|P]] は、[[チューリング機械]]で[[多項式時間]]で解ける決定問題の集合である。このクラスは、直感的に言えば最悪の場合でも効率的に解くことができる問題である<ref name="Sipser2006">{{cite book|last=Sipser|first=Michael|title=Introduction to the Theory of Computation|edition=2nd edition|chapter=Time Complexity|date=2006年|publisher=Thomson Course Technology|location=USA|id=ISBN 0-534-95097-3}}</ref>。
| |
| − | | |
| − | 複雑性クラス '''[[NP]]''' は、[[非決定性チューリング機械]]で多項式時間で解ける決定問題の集合である。このクラスには効率的に解くことが望ましいとされる様々な問題が含まれている。例えば、[[充足可能性問題]]、[[ハミルトン閉路問題]]、[[頂点被覆問題]]などである。このクラスの全問題は、その解法を効率的に検証する方法があるという特徴を持つ<ref name="Sipser2006"/>。
| |
| − | | |
| − | 多くの複雑性クラスは、それを表現するのに必要となる[[形式体系|論理体系]]によって特徴付けられる。これは、[[記述計算量]]の概念と関係がある。
| |
| − | | |
| − | 各クラスに対し、そのクラスの'''完全問題'''を考えることがある。クラス''C''の完全問題とは''C''に属する問題のうちで最も計算するのが難しい問題のことである。具体的な定義は以下のようになる。
| |
| − | | |
| − | ; —困難 ({{lang-en-short|— hard}})
| |
| − | :クラス''C''に対して、問題''P''が''C'''''困難'''であるとは、''C''に属する任意の問題を''P''に帰着（多くの場合[[多項式時間変換|多項式時間帰着]]を考えるが、そうでない場合もある<!--NP完全問題の定義としてlog space帰着を採用する場合もある-->）できるということである。すなわち''P''は''C''に属するいかなる問題よりも、同等かそれ以上に難しいということである。ただし、''C'''''完全'''と異なり、''P''自身は''C''に属するとは限らない。
| |
| − | ; —完全 ({{lang-en-short|— complete}})
| |
| − | :クラス''C''に対して、問題''P''が''C'''''完全'''であるとは、''P''が''C''に属しかつ''C''困難ということである。すなわち''P''は''C''に属する問題の中で、本質的に最も難しい問題であるということである。
| |
| − | | |
| − | === 主な複雑性クラス ===
| |
| − | * [[L (計算複雑性理論)|L]]
| |
| − | * [[NL (計算複雑性理論)|NL]]
| |
| − | * [[NC (計算複雑性理論)|NC]]
| |
| − | * [[P (計算複雑性理論)|P]]
| |
| − | * [[NP]]（[[NP困難]], [[NP完全]]）
| |
| − | * [[co-NP]]
| |
| − | * [[PSPACE]]
| |
| − | * [[EXPTIME]]
| |
| − | * [[BPP (計算複雑性理論)|BPP]]
| |
| − | * [[BQP]]
| |
| − | | |
| − | == 未解決の問題 ==
| |
| − | === P<nowiki> = </nowiki>NP 問題 ===
| |
| − | {{Main|P≠NP予想}} | |
| − | | |
| − | NPがPと同じかどうかという疑問（換言すれば、非決定的な多項式時間で解くことのできる問題は決定的な多項式時間でも解くことができるか）は、理論計算機科学における最重要問題の1つであり、その解決が様々な意味を持っている<ref name="Sipser2006"/>。同じであった場合に都合が悪い影響として、[[暗号理論]]の多くがNPの困難さに依存しているため、Pと同じであることが判明すると使い物にならなくなるのである。しかし、よい影響も多々あり、様々な重要な問題に効率的な解法があることが明らかとなることが重要である。例えば、[[オペレーションズリサーチ]]における[[整数計画問題]]、物流合理化、[[生物学]]における[[タンパク質構造予測]]、[[純粋数学]]の定理を[[計算機]]で効率的に形式的に証明する可能性などがある<ref>{{cite journal|title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete.|last=Berger|first=Bonnie A.|coauthors=Leighton, Terrance|journal=Journal of Computational Biology|date=1998年|volume=5|number=1|pages=p27-40}}、[http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?cmd=Retrieve&db=pubmed&dopt=Abstract&list_uids=9541869&query_hl=14&itool=pubmed_docsum PubMed]</ref><ref>{{cite journal|last=Cook|first=Stephen|authorlink=スティーブン・クック|title=The P versus NP Problem|publisher=[[クレイ数学研究所]]|date=2000年|month=April|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|accessdate=2006-10-18}}</ref>。[[クレイ数学研究所]]は[[2000年]]に、この問題を最初に解いた人に100万ドルを支払うと発表した<ref>{{cite journal|title=The Millennium Grand Challenge in Mathematics|last=Jaffe|first=Arthur M.|journal=Notices of the AMS|volume=53|issue=6|url=http://www.ams.org/notices/200606/fea-jaffe.pdf|accessdate=2006-10-18}}</ref>。
| |
| − | | |
| − | この問題を考えるにあたって重要となるのは、[[NP完全問題|NP完全]]の概念である。NP完全な問題はNPの中では最もPから遠い問題ということになる。P<nowiki> = </nowiki>NPが証明されていないため、ある問題をNP完全と判明している問題に[[還元 (計算複雑性理論)|還元]]できるということは、その問題の多項式時間の解法が未知であることを示している。逆に、すべての NP問題はNP完全問題に還元できるため、NP完全問題の多項式時間の解法を発見すれば、P<nowiki> = </nowiki>NPが証明される<ref name="Sipser2006"/>。（一方、たとえP<nowiki> = </nowiki>NPが成立しても、[[NP困難]]な問題は多項式時間で解けるとは限らない。理由はNP困難のページを参照のこと）
| |
| − | | |
| − | === NPにおける不完全問題 ===
| |
| − | 上の問題に関連して、NPクラスに属する問題でPクラスには属しないがNP完全でもない問題は存在するか、という問題もある。つまり、非決定的な多項式時間の解法はあるが、NP完全問題から多項式時間で還元できない問題ということである。このような問題のクラスを{{仮リンク|NP-intermediate|en|NP-intermediate}}と呼び、候補として[[同型グラフ|グラフ同型問題]]や[[素因数分解|整数の因数分解]]、[[離散対数問題]]などがある。もしP<nowiki> ≠ </nowiki>NPが真ならば、そのような問題が存在することが証明されている<ref name="DuKo2000">{{cite book|last=Du|first=Ding-Zhu|coauthors=Ko, Ker-I|title=Theory of Computational Complexity|publisher=John Wiley & Sons|date=2000年|country=USA|id=ISBN 978-0-471-34506-0}}</ref>。
| |
| − | | |
| − | === NP<nowiki> = </nowiki>co-NP ===
| |
| − | '''[[co-NP]]'''クラスはNP問題の[[補問題]]の集合である（すなわち、「はい」と「いいえ」が逆転している問題）。両者は等しくないと考えられているが証明されていない。2つの複雑性クラスが等しくないことが判明すると、NP完全問題は co-NP には含まれず、co-NP完全問題は NP には含まれないことが明らかになる<ref name="DuKo2000"/>。
| |
| − | | |
| − | ==イントラクタブル==
| |
| − | {{see also|組合せ爆発}}
| |
| − | 理論上計算可能な問題であっても、実際に解くことができない問題を'''イントラクタブル''' ({{lang-en-short|intractable}}, 手に負えない、処理しにくい) であるという。「実際に」解けるとはどういうことかという問題もあるが、多項式時間の解法がある問題が一般に（小さな入力だけでなく）解けるとされている。イントラクタブルな問題として知られているものとしては、'''[[EXPTIME]]'''完全な問題がある。NP が P と同じでなかった場合、NP完全な問題もイントラクタブルだということになる。
| |
| − | | |
| − | [[指数関数時間]]の解法がなぜ実際には使えないかを考えるため、2<sup>''n''</sup> 回の操作を必要とする問題を考える（''n'' は入力のサイズである）。比較的小さな入力数 ''n'' = 100 のときについて、1秒間に 10<sup>10</sup>（10 [[ギガ]]）回命令を実行できる計算機を想定すると、その問題を解くには約 4 × 10<sup>12</sup> 年かかる。これは現在の[[宇宙#宇宙の年齢・大きさ|宇宙の年齢]]よりも長い。
| |
| − | | |
| − | == 主な研究者 ==
| |
| − | * [[マヌエル・ブラム]]: [[ブラムの公理]]に基づいた公理的複雑性理論を構築した
| |
| − | * [[スティーブン・クック]]
| |
| − | * [[ユリス・ハルトマニス]]
| |
| − | * [[リチャード・カープ]]
| |
| − | * [[アディ・シャミア]]
| |
| − | * [[リチャード・スターンズ]]
| |
| − | * [[アンドリュー・チーチー・ヤオ]]
| |
| − | * [[レスリー・ヴァリアント]]
| |
| − | * {{ill2|Leonid Levin|en|Leonid Levin}}
| |
| − | | |
| − | == 脚注 ==
| |
| − | {{reflist}}
| |
| − | | |
| − | == 参考文献 ==
| |
| − | * L. Fortnow, Steve Homer (2002/2003). [http://people.cs.uchicago.edu/~fortnow/papers/history.pdf A Short History of Computational Complexity]. In D. van Dalen, J. Dawson, and A. Kanamori, editors, ''The History of Mathematical Logic''. North-Holland, Amsterdam.
| |
| − | * Jan van Leeuwen, ed. ''Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity'', The MIT Press/Elsevier, 1990. ISBN 978-0-444-88071-0 (Volume A). QA 76.H279 1990. 解説が豊富で、様々な文献で引用・参照されている。
| |
| − | | |
| − | == 関連項目 ==
| |
| − | * [[P≠NP予想]]
| |
| − | * [[多項式時間]]
| |
| − | * [[加速定理]]
| |
| − | * [[理論計算機科学]]
| |
| − | * [[還元 (計算複雑性理論)]]
| |
| − | | |
| − | == 外部リンク ==
| |
| − | * [https://complexityzoo.uwaterloo.ca/Complexity_Zoo The Complexity Zoo] - 複雑性理論に関するWiki
| |
| − | * [http://www.cs.princeton.edu/theory/complexity/ Free (at least for now) book on computational complexity]
| |
| − | | |
| − | {{Computer-stub}}
| |
| − | {{デフォルトソート:けいさんふくさつせいりろん}}
| |
| − | [[Category:計算複雑性理論|*]]
| |
| − | [[Category:理論計算機科学]]
| |
| − | [[Category:計算理論]]
| |
| − | [[Category:組合せ最適化]]
| |
| − | [[Category:数学に関する記事]]
| |