Intractabilityと組合せ爆発
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/08 08:13 UTC 版)
「人工知能の歴史」の記事における「Intractabilityと組合せ爆発」の解説
1971年のスティーブン・クックの定理（英語版）に基づき、1972年、リチャード・カープが指数関数時間（入力のサイズに対して指数関数的になる時間）でしか解けない問題が多数あることを示した (en)。それらの問題の最適解を求めるには、問題がごく小さい場合を除いて極めて多大な処理時間を要する。これは、AIプログラムが「おもちゃ」のような問題に適用している解法の多くを、そのままスケールアップしても使えないことを意味していた。
※この「Intractabilityと組合せ爆発」の解説は、「人工知能の歴史」の解説の一部です。
「Intractabilityと組合せ爆発」を含む「人工知能の歴史」の記事については、「人工知能の歴史」の概要を参照ください。
ウィキペディア小見出し辞書の「Intractabilityと組合せ爆発」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- Intractabilityと組合せ爆発のページへのリンク
