複雑性の応用
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/03/25 14:40 UTC 版)
計算複雑性理論は、問題の複雑性、すなわち問題を解くことの困難さを研究する。問題はそれを解くアルゴリズムにかかる時間を問題の大きさの関数で表すことによって複雑性クラスに分類できる。当然ながら問題は難しいものも簡単なものもある。例えば、難しい問題ではその大きさに対して解くのに指数時間かかるアルゴリズムを必要とする。そのような問題として例えば巡回セールスマン問題がある。これを解くのにかかる時間は O ( n 2 2 n ) {\displaystyle O(n^{2}2^{n})} （ここで nはネットワークの大きさであり、セールスマンが訪問すべき都市の数）である。都市のネットワークが大きくなると、解である経路を求めるのにかかる時間は指数関数以上に急激に増大する。 問題が理論上解くことができるとしても、実際にはそれほど単純な話ではない。その問題は非常に長い時間とあまりにも大量の空間を必要とするかもしれない。計算複雑性理論には様々な観点があり、問題を解くのにかかる時間、メモリ、その他の資源を研究する。問題の複雑性を分析する上では、時間と空間が最も重要でよく研究されている。 理論上は解けるが、必要とする時間や空間があまりにも大きいため、事実上解こうとすることが現実的でない問題のクラスも存在する。そのような問題をイントラクタブル（手に負えない、処理しにくい）という。
※この「複雑性の応用」の解説は、「複雑性」の解説の一部です。
「複雑性の応用」を含む「複雑性」の記事については、「複雑性」の概要を参照ください。
ウィキペディア小見出し辞書の「複雑性の応用」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 複雑性の応用のページへのリンク
