AI-повна задача

У галузі штучного інтелекту, найскладніші задачі неформально називають AI-повними (англ. AI-complete, AI-hard), наголошуючи на тому, що обчислювальна складність цих задач еквівалентна складності вирішення головного завдання штучного інтелекту— створення комп'ютерів, настільки ж розумних, як і люди. Задача, котру називають AI-повною, вважається такою, що не може бути розв'язаною за допомогою простого алгоритму.

AI-повними задачами вважаються комп'ютерний зір, розуміння природної мови і розв'язання задач реального життя за непередбачуваних обставин, що при цьому виникають.

На даний момент AI-повні задачі не можуть бути розв'язані лише за допомоги сучасних комп'ютерних технологій без використання людино-орієнтованих обчислень. Ця властивість може бути корисною, наприклад, для перевірки присутності людини за допомогою тесту CAPTCHA, а також в галузі комп'ютерної безпеки для запобігання атакам методом «грубої сили».

Історія

Термін було запропоновано Фанею Монталво за аналогією до NP-повних та NP-складних задач в теорії складності обчислень, що формально описує найвідоміші класи складних задач. 1987 року Ерік Мюллер одним із перших використовує термін у своїй дисертації пізніше, 1991 року, Ерік Реймонд додає його до свого енциклопедичного словника комп'ютерного сленгу Jargon File.

AI-повні задачі

До класу AI-повних задач належать:

• Комп'ютерний зір (в тому числі, розпізнавання об'єктів)
• Розпізнавання природної мови (в тому числі, інтелектуальний аналіз тексту, машинний переклад і розв'язання лексичних неоднозначностей)
• Розв'язання задач реального життя за непередбачуваних обставин, що при цьому виникають, зокрема, навігація, планування та навіть своєрідна форма мислення, здійснювана експертними системами.

Машинний переклад

Для точного перекладу, машина повинна розуміти текст. Вона повинна відслідковувати хід думки автора, а отже, певним чином, вона має мислити. Машина повинна мати широкий спектр знань (а також здоровий глузд), щоб розуміти про що йде мова — вона, щонайменше, має бути ознайомлена зі всіма базовими фактами, що відомі пересічному перекладачу-людині. Хоч деякі знання можуть бути явно відображені в комп'ютері, інші є скоріш несвідомими і тісно пов'язаними з людським тілом: до прикладу, машина має зрозуміти, що ми відчуваємо, дивлячись на океан, щоб правильно перекласти відповідну метафору. Вона також повинна створити модель цілей, намірів, переживань та емоцій автора, щоб якомога краще передати їх засобами нової мови. Іншими словами, для якісного перекладу, машина має володіти рядом інтелектуальних здібностей, притаманних людині, зокрема мисленням, здоровим глуздом, а також інтуїтивними відчуттями, що лежать в основі рухів та маніпуляцій об'єктами, сприйняття, та соціальних навичок. Таким чином, машинний переклад вважається AI-повною задачею: вона вимагає від машини інтелекту майже людського рівня.

Крихкість програмного забезпечення

Наразі системи штучного інтелекту можуть розв'язувати лише дуже спрощені й обмежені варіанти AI-повних задач. Коли дослідники штучного інтелекту намагаються адаптувати свої системи до роботи з більш складними проблемами, що виникають в реальному житті, без своєрідного здорового глузду чи елементарного розуміння ситуації, програми, здебільшого, стають неймовірно крихкими: вони зазнають невдачі, як тільки з'являються непередбачувані обставини за межами проблеми, на яку вони розраховані. Коли люди мають справу з новими життєвими ситуаціями, їм сприяє той факт, що вони знають, чого чекати: знають про всі предмети, що їх оточують, чому вони там, для чого вони, скоріш за все, призначені і т. д. Людина може розпізнати незнайоме і незвичне, щоб пристосуватись до нього. Машина без сильного (майже людського) штучного інтелекту не має жодних додаткових знань чи вмінь для розв'язання тої чи іншої проблеми.

Формалізація

Теорія складності обчислень займається відносною складністю обчислюваних функцій. За визначенням, вона не розглядає проблем, рішення яких невідоме чи формально не визначене. Позаяк багато задач штучного інтелекту ще не формалізовано, звичайної теорії складності не достатньо для формального визначення AI-повноти.

Для розв'язання цієї проблеми було запропоновано Теорію складності штучного інтелекту. В її основі лежить модель обчислень, що розподіляє тягар обчислень між комп'ютером і людиною: частина обчислень виконується комп'ютером, інша — людиною. Ця модель формалізується Машиною Тюрінга з людиною-асистентом. Така формалізація визначає складність алгоритмів, складність задач та проблему звідності, що, в свою чергу, дозволяє визначити класи еквівалентності.

Складність виконання алгоритму Машиною Тюрінга з людиною-асистентом задається парою $\langle \Phi _{H},\Phi _{M}\rangle$, перший елемент якої позначає складність людської частини обчислень, а другий — складність обчислень, здійснюваних машиною.

Результати

Складність розв'язання деяких відомих зачач за допомогою Машини Тюрінга з людиною-асистентом:

• Оптичне розпізнавання символів друкованого тексту: $\langle O(1),poly(n)\rangle$
• Тест Тюрінга:
  • для послідовності з $n$ бесід, якщо суддя пам'ятає історію цих бесід (наполегливий суддя): $\langle O(n),O(n)\rangle$
  • для послідовності з $n$ бесід, якщо історія цих бесід має передаватись повторно: $\langle O(n),O(n^{2})\rangle$
  • для послідовності з $n$ бесід, якщо історія цих бесід має передаватись повторно, а для прочитання запиту потрібен лінійний час: $\langle O(n^{2}),O(n^{2})\rangle$
• ESP гра: $\langle O(n),O(n)\rangle$
• Маркування зображень (згідно з Протоколом Артура-Мерліна): $\langle O(n),O(n)\rangle$
• Категоризація зображень: лише людиною: $\langle O(n),O(n)\rangle$, з людською допомогою: $\langle O(\log n),O(n\log n)\rangle$.

Див. також

• Обчислювальна складність
• Теорія складності обчислень
• Штучний інтелект
• Експертні системи
• Обробка природної мови
• Комп'ютерний зір
• Машинний переклад