AI-полная задача

Термин был введён Фаня Монталво по аналогии с NP-полными и NP-трудными задачами в теории вычислительной сложности, которая формально описывает класс наиболее известных трудных задач^[4]. Первые случаи употребления термина встречаются в диссертации Эрика Мюллера 1987 года^[5] и в «Jargon File» Эрика Рэймонда (1991)^[6].

Экспертные системы, популярные в 1980-х годах, могли решать очень упрощённые и/или ограниченные версии AI-полных задач, но не задачи в целом. Попытки исследователей ИИ «масштабировать» свои системы на более сложные привычные условия приводили к чрезмерной ломкости программ без здравого смысла или хотя бы rudimentary-уровня понимания ситуации: программы выходили из строя, если начинали возникать непредвиденные обстоятельства вне исходной предметной области. Человек в новых обстоятельствах опирается на знание общего контекста — понимает, что его окружает, зачем и как устроено, способен распознавать необычные ситуации и приспосабливаться. Экспертные системы же были негибки при столкновении с новыми условиями^[7].

В мае 2022 года компания DeepMind представила работу, где одна модель обучалась одновременно выполнять несколько задач. Эта модель, названная Gato, способна «играть в Atari, подписывать изображения, вести диалог, собирать башни из кубиков с помощью настоящей роботизированной руки и многое другое, выбирая в зависимости от контекста: выводить текст, управляющие усилия, нажатия кнопок или прочие токены»^[8]. Аналогично, задачи, которые ранее считались AI-полными, такие как машинный перевод^[9], теперь реализованы в больших языковых моделях^[10].

К AI-полным гипотетически относятся:

• AI рецензирование научных работ^[11] (комплексное понимание естественного языка, автоматическое рассуждение, автоматическое доказательство теорем, формализованная логика с элементами экспертной системы)
• Задача Бонгарда^[12]
• Машинное зрение (и подзадачи типа распознавание объектов)^[13]
• Автоматическое понимание естественного языка (и подзадачи такие как текстовый майнинг^[14], машинный перевод^[15], и разрешение лексической многозначности^[16])
• Автономное вождение
• Обработка неожиданных обстоятельств при решении любых реальных задач^[17], будь то робототехническая навигация, планирование или даже рассуждение типа, реализуемого экспертными системами.

Теория вычислительной сложности рассматривает относительную вычислительную сложность различных вычислимых функций. Однако, по определению, она не охватывает задачи, решение которых неизвестно или формально не описано. Поскольку многие задачи ИИ до сих пор не имеют строгой формализации, традиционная теория сложности не позволяет формально определить AI-полноту.

Роман Ямпольский^[18] предложил определять задачу ${\displaystyle C}$ как AI-полную, если выполняются два условия:

• Она принадлежит набору задач ИИ (решаемых человеком-экспертом).
• Любая задача ИИ может быть сведена к ${\displaystyle C}$ за полиномиальное время.

В свою очередь, задача ${\displaystyle H}$ называется AI-трудной, если существует AI-полная задача ${\displaystyle C}$, к которой ${\displaystyle H}$ приводится за полиномиальное время с помощью Тьюринг-редукции. Такой подход также вводит понятие AI-простых задач — решаемых за полиномиальное время детерминированной машиной Тьюринга с оракулом для заданной задачи.

Ямпольский^[19] также высказывал гипотезу, что тест Тьюринга представляет собой определяющий признак AI-полноты.

Гроппе и Джейн^[20] относят к AI-полным такие задачи, для решения которых требуется универсальный искусственный интеллект, а современные системы способны лишь к частичному решению ограниченных версий этих задач. По мнению Шекрст^[12], нахождение полиномиального решения для AI-полных задач не обязательно означает решение проблемы универсального ИИ, а главным ограничением считается недостаток исследований в области вычислительной сложности.

Кви-Бинторо и Велес^[21] подчёркивают, что решение AI-полных задач окажет существенное влияние на общество.