У галузі штучного інтелекту найскладніші задачі неформально називають AI повними англ AI complete AI hard наголошуючи на

У галузі штучного інтелекту, найскладніші задачі неформально називають 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$
: $\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$ .

Див. також

Примітки

Shapiro, Stuart C. (1992). Artificial Intelligence [ 13 травня 2019 у Wayback Machine.] In Stuart C. Shapiro (Ed.), Encyclopedia of Artificial Intelligence (Second Edition, pp. 54–57). New York: John Wiley. (Section 4 is on «AI-Complete Tasks».)
Roman V. Yampolskiy. Turing Test as a Defining Feature of AI-Completeness . In Artificial Intelligence, Evolutionary Computation and Metaheuristics (AIECM) --In the footsteps of Alan Turing. Xin-She Yang (Ed.). pp. 3-17. (Chapter 1). Springer, London. 2013. http://cecs.louisville.edu/ry/TuringTestasaDefiningFeature04270003.pdf [ 22 травня 2013 у Wayback Machine.]
Luis von Ahn, Manuel Blum, Nicholas Hopper, and John Langford. CAPTCHA: Using Hard AI Problems for Security [ 4 березень 2016 у Wayback Machine.]. In Proceedings of Eurocrypt, Vol. 2656 (2003), pp. 294—311.
Bergmair Richard. Natural Language Steganography and an "AI-complete" Security Primitive. — 2006. — 7 січня. — (CiteSeerX): 10.1.1.105.129. (unpublished?)
Mallery, John C. (1988), Thinking About Foreign Policy: Finding an Appropriate Role for Artificially Intelligent Computers, , St. Louis, MO, архів оригіналу за 29 лютого 2008, процитовано 24 травня 2015.
Mueller, Erik T. (1987, March). Daydreaming and Computation (Technical Report CSD-870017)^{[недоступне посилання з лютого 2019]} Ph.D. dissertation, University of California, Los Angeles. («Daydreaming is but one more AI-complete problem: if we could solve any one artificial intelligence problem, we could solve all the others», p. 302)
Raymond, Eric S. (1991, March 22). Jargon File Version 2.8.1 [ 4 червня 2011 у Wayback Machine.] (Definition of «AI-complete» first added to jargon file.)
Lenat, Douglas; Guha, R. V. (1989), Building Large Knowledge-Based Systems, Addison-Wesley, с. 1—5
Dafna Shahaf and Eyal Amir (2007) Towards a theory of AI completeness [Архівовано 24 серпень 2007 у wayback.archive-it.org]. Commonsense 2007, 8th International Symposium on Logical Formalizations of Commonsense Reasoning [ 19 січня 2021 у Wayback Machine.].

[Shapiro92-1] Shapiro, Stuart C. (1992). Artificial Intelligence [ 13 травня 2019 у Wayback Machine.] In Stuart C. Shapiro (Ed.), Encyclopedia of Artificial Intelligence (Second Edition, pp. 54–57). New York: John Wiley. (Section 4 is on «AI-Complete Tasks».)

[2] Roman V. Yampolskiy. Turing Test as a Defining Feature of AI-Completeness . In Artificial Intelligence, Evolutionary Computation and Metaheuristics (AIECM) --In the footsteps of Alan Turing. Xin-She Yang (Ed.). pp. 3-17. (Chapter 1). Springer, London. 2013. http://cecs.louisville.edu/ry/TuringTestasaDefiningFeature04270003.pdf [ 22 травня 2013 у Wayback Machine.]

[3] Luis von Ahn, Manuel Blum, Nicholas Hopper, and John Langford. CAPTCHA: Using Hard AI Problems for Security [ 4 березень 2016 у Wayback Machine.]. In Proceedings of Eurocrypt, Vol. 2656 (2003), pp. 294—311.

[4] Bergmair Richard. Natural Language Steganography and an "AI-complete" Security Primitive. — 2006. — 7 січня. — (CiteSeerX): 10.1.1.105.129. (unpublished?)

[5] Mallery, John C. (1988), Thinking About Foreign Policy: Finding an Appropriate Role for Artificially Intelligent Computers, , St. Louis, MO, архів оригіналу за 29 лютого 2008, процитовано 24 травня 2015.

[6] Mueller, Erik T. (1987, March). Daydreaming and Computation (Technical Report CSD-870017)^{[недоступне посилання з лютого 2019]} Ph.D. dissertation, University of California, Los Angeles. («Daydreaming is but one more AI-complete problem: if we could solve any one artificial intelligence problem, we could solve all the others», p. 302)

[7] Raymond, Eric S. (1991, March 22). Jargon File Version 2.8.1 [ 4 червня 2011 у Wayback Machine.] (Definition of «AI-complete» first added to jargon file.)

[8] Lenat, Douglas; Guha, R. V. (1989), Building Large Knowledge-Based Systems, Addison-Wesley, с. 1—5

[ucl.ac.uk-9] Dafna Shahaf and Eyal Amir (2007) Towards a theory of AI completeness [Архівовано 24 серпень 2007 у wayback.archive-it.org]. Commonsense 2007, 8th International Symposium on Logical Formalizations of Commonsense Reasoning [ 19 січня 2021 у Wayback Machine.].