Запис атласу: https://www.aitimeline.dev/uk/events/evt-0121/
Дослідження · травень 1971 р.
Теорема Кука
Кук показав, що задача виконуваності булевої формули — найважча у своєму класі: до неї зводиться будь-яка задача, розв'язок якої можна швидко перевірити.
Чому це важливо
З'явилася межа між «можна перевірити» і «можна знайти» — питання, яке досі визначає, що від машини взагалі варто вимагати.
Робота вводить поняття, яке згодом назвали NP-повнотою, і ставить питання P проти NP. Для ШІ це не абстракція: пошук у просторі станів, виконання обмежень і виведення в логіці першого порядку — усе це задачі тієї самої природи. Евристики потрібні не тому, що алгоритми недосконалі, а тому, що точний перебір нездійсненний у принципі.
Відомості про подію
- Дата події
- травень 1971 р.
- Дата на часовій осі
- Дата події
- Перевірка
- Джерела зібрано автоматично · 17 вересня 2026 р.
- Лінії
- ID
- evt-0121
Доповідь на третьому симпозіумі ACM з теорії обчислень, травень 1971 року.
Пов’язані події
Раніше
- Пов’язано Принцип резолюції 1965
Стаття формулює результат саме про складність процедур доведення теорем.
- Пов’язано Процедура Девіса — Патнема з розщепленням 1961посилається на цей запис
Процедура перевіряє виконуваність формул логіки висловлень — саме ту задачу, яку теорема Кука 1971 року зробила зразком складної.
Пізніше
- Спирається на Двадцять одна задача Карпа 1972посилається на цей запис
Стаття прямо спирається на результат Кука і зводить до нього 21 задачу.
- Спирається на Теорія навченого 1984посилається на цей запис
Навченість визначено через існування алгоритму, що працює за поліноміальний час.