AI完全

人工知能（AI）の分野では、汎用人工知能による解決が想定されるタスクは、非公式にはAI完全またはAI困難として知られています。^{[ 1 ]}問題をAI完全と呼ぶことは、単純な特定のアルゴリズムでは解決できないという信念を反映しています。

2013年以前は、AIで解決できると考えられていた問題には、コンピュータビジョン、自然言語理解、現実世界の問題を解決する際に予期せぬ状況に対処することなどが含まれていました。^{[ 2 ]} AIで解決できるタスクは、 CAPTCHAが目指すように、人間と自動化されたエージェントを区別するのに役立つと特に考えられていました。 ^{[ 3 ]}

この用語は、ファニャ・モンタルボが複雑性理論におけるNP完全性やNP困難性との類推から造語したもので、最も有名な難問のクラスを形式的に記述するものである。^{[ 4 ]}この用語の初期の使用例は、エリック・ミューラーの1987年の博士論文^{[ 5 ]}とエリック・レイモンドの1991年のジャーゴンファイル^{[ 6 ]}にある。

1980年代に流行したエキスパートシステムは、AI完全問題の非常に単純なバージョンや限定されたバージョンを解決することはできましたが、完全な汎用性では決して解決できませんでした。AI研究者が、より複雑な現実世界の状況に対応するためにシステムを「スケールアップ」しようとしたとき、常識的な知識や状況の基本的な理解がないと、プログラムは過度に脆弱になる傾向がありました。つまり、元の問題のコンテキスト外の予期せぬ状況が現れ始めると、プログラムは失敗してしまうのです。人間が世界で新しい状況に対処するとき、一般的なコンテキストを認識することで助けられます。周囲のものが何であるか、なぜそこにあるのか、何をする可能性が高いかなどを知っているからです。人間は異常な状況を認識し、それに応じて調整することができます。エキスパートシステムにはこのような適応性がなく、新しい状況に直面すると脆弱でした。^{[ 7 ]}

DeepMindは2022年5月に、複数のことを同時に行うように単一のモデルを訓練した研究を発表しました。Gatoと名付けられたこのモデルは、「 Atariで遊んだり、画像にキャプションを付けたり、チャットしたり、実際のロボットアームでブロックを積み重ねたり、その他多くのことができ、コンテキストに基づいてテキスト、関節トルク、ボタンの押下、またはその他のトークンを出力するかどうかを決定します。」^{[ 8 ]}同様に、機械翻訳^{[ 9 ]}のように、かつてはAIで完了すると考えられていたタスクの一部は、大規模言語モデルの能力に含まれています。^{[ 10 ]}

AI完全問題には以下のようなものが含まれると仮説が立てられている。

• AIピアレビュー^{[ 11 ]}（複合的な自然言語理解、自動推論、自動定理証明、形式化された論理エキスパートシステム）
• ボンガード問題^{[ 12 ]}
• コンピュータビジョン（および物体認識などのサブ問題）^{[ 13 ]}
• 自然言語理解（およびテキストマイニング^{[ 14 ]} 、機械翻訳[ ^{15 ] 、}単語の意味曖昧性解消^{[ 16 ]}などのサブ問題）
• 自動運転^{[ 17 ]}
• 現実世界のあらゆる問題を解決する際に予期せぬ状況に対処すること^{[ 18 ]}、ナビゲーション、計画、エキスパートシステムによる推論など。

計算複雑性理論は、計算可能な関数の相対的な計算難易度を扱う。定義上、解が不明な問題や形式的に特徴付けられていない問題は対象外である。多くのAI問題はまだ形式化されていないため、従来の複雑性理論ではAIの完全性を形式的に定義することはできない。

Roman Yampolskiy ^{[ 19 ]} は、問題が${\displaystyle C}$AI完全であるとは、以下の2つの特性を備えている場合をいう。

• これはAI問題群（人間によるオラクル解決可能問題）に含まれる。
• あらゆるAI問題を変換できます${\displaystyle C}$多項式時間アルゴリズムによって。

一方、問題点${\displaystyle H}$AI-Hardであるのは、AI-Complete問題が存在する場合に限る。${\displaystyle C}$それは多項式時間でチューリング還元可能であり、${\displaystyle H}$このことから、ある問題に対するオラクルを備えた決定性チューリングマシンによって多項式時間で解けるAI-Easy問題の存在も導かれる。

ヤンポルスキー^{[ 20 ]}は、チューリングテストがAIの完全性を定義する特徴であるとも仮説を立てている。

GroppeとJain ^{[ 21 ]}は、人間レベルの機械性能に到達するために人工汎用知能を必要とする問題をAI完全問題として分類しているが、現在のAIシステムではAI完全問題の限定版しか解決できない。Šekrst ^{[ 12 ]}によれば、AI完全問題の多項式解を得ることは、必ずしも人工汎用知能の問題を解決することと同義ではなく、計算複雑性研究の不足が人工汎用知能の実現を阻む要因であると強調している。

Kwee-BintoroとVelez ^{[ 22 ]}によれば、 AI完全問題を解決することは社会に大きな影響を与えるだろう。

• ASR完了
• コンピュータサイエンスにおける未解決問題一覧
• 人工知能