計算機科学における計算量の爆発
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 06:55 UTC 版)
「組合せ爆発」の記事における「計算機科学における計算量の爆発」の解説
計算機科学において、計算複雑性理論は重要な研究テーマである。たとえ解が存在して計算方法があっても、現実的なCPU数やメモリ容量の計算資源を使って、入力問題のサイズの多項式関数で表せるほどの短時間には解けないほど複雑な計算問題が存在する。複雑性クラスにはさまざまあるが、多項式関数の時間で解けない場合は計算量が爆発すると言われる。計算問題が組合せを内包している場合に組合せ爆発または組合せ的爆発といい、また指数関数のサイズになる場合に指数的爆発（exponential explosion）という。
※この「計算機科学における計算量の爆発」の解説は、「組合せ爆発」の解説の一部です。
「計算機科学における計算量の爆発」を含む「組合せ爆発」の記事については、「組合せ爆発」の概要を参照ください。
ウィキペディア小見出し辞書の「計算機科学における計算量の爆発」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 計算機科学における計算量の爆発のページへのリンク
