|
具体的には、計算複雑性理論は「あるアルゴリズムへの入力データの長さを増やしたとき、実行時間や必要な記憶量はどのように増えるか？」という問いに答える。これは、[[計算機]]の実際的な限界を与えるものであり、この理論は産業や社会にとって重要な意味を持つ。なぜならば、計算機の性能は向上しているが、解析すべき情報も増加しているため、アルゴリズムが入力データ長の増大にうまく対応できるか否かで、計算機が現実的な問題を解決するのに役に立つか否かが決まるからである。
計算複雑性理論では、計算問題やそれを解くアルゴリズムを、'''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予想の証明は重要とされているのである。
== 計算問題と計算量・複雑性 ==
ある量の計算資源を使って解くことができるすべての計算問題の集合を[[複雑性クラス]]という。
複雑性クラス [[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"/>。
{{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における不完全問題 ===
上の問題に関連して、'''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|組合せ爆発}}
理論上計算可能な問題であっても、実際に解くことができない問題を'''イントラクタブル'''<ref>{{lang-en-short|intractable}}、手に負えない、処理しにくい。</ref>であるという。「実際に」解けるとはどういうことかという問題もあるが、多項式時間の解法がある問題が一般に（小さな入力だけでなく）解けるとされている。イントラクタブルな問題として知られているものとしては、'''[[EXPTIME]]'''完全な問題がある。'''NP''' が '''P''' と同じでなかった場合、'''NP'''完全な問題もイントラクタブルだということになる。
[[指数関数時間]]の解法がなぜ実際には使えないかを考えるため、<math>2^n</math> 回の操作を必要とする問題を考える（<math>n</math> は入力のサイズである）。比較的小さな入力数 <math>n = 100</math> のときについて、1秒間に <math>10^{10}</math> （10 [[ギガ]]）回命令を実行できる計算機を想定すると、その問題を解くには約 <math>4\times{}10^{12}</math> 年かかる。これは現在の[[宇宙#宇宙の年齢・大きさ|宇宙の年齢]]よりも長い。
| 