Задача здійсненності булевих формул: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
м вікіфікація |
||
Рядок 4:
Задача полягає в наступному: чи можна призначити усім змінним, що зустрічаються у формулі, значення ''хибність'' і ''істина'' так, щоб формула стала істинною.
Згідно з [[Теорема Кука — Левіна|теоремою Кука]], доведеною [[Стівен Кук|Стівеном Куком]] в 1971-му році, задача SAT для булевих формул, записаних в [[Кон'юнктивна нормальна форма|кон'юнктивній нормальній формі]], є [[NP-повна задача|NP-повною]]. Вимога про запис в кон'юнктивній формі є важливою, оскільки, наприклад, завдання SAT для формул, представлених в [[Диз'юнктивна нормальна форма|диз'юнктивній нормальній формі]], тривіально вирішується за лінійний час залежно від розміру запису формули.
== Точне формулювання ==
Рядок 18:
У 1971-му році в статті [[Стівен Кук|Стівена Кука]] був уперше введений термін «[[NP-повна задача]]», і задача SAT була першою задачею, для якого доводилася ця властивість.
У доказі [[Теорема Кука — Левіна|теореми Кука]] кожна задача з [[Клас складності NP|класу NP]] в явному виді зводиться до SAT. Після появи результатів, Куком була доведена NP-повнота для безлічі інших задач. При цьому найчастіше для доказу NP-повноти деякої задачі наводиться [[поліноміальне зведення]] задачі SAT до цієї задачі, можливо в декілька кроків, тобто з використанням декількох проміжних задач.
== Окремі випадки задачі SAT ==
| |||