Вікіпедія

Задача здійсненності булевих формул: відмінності між версіями

Інтерактивний перегляд історії
[неперевірена версія][неперевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Немає опису редагування
м replaced: Згідно [ → Згідно з [ за допомогою AWB
Рядок 4:
Задача полягає в наступному: чи можна призначити усім змінним, що зустрічаються у формулі, значення ''хибність'' і ''істина'' так, щоб формула стала істинною.
 
Згідно з [[Теорема Кука|теоремітеоремою Кука]], доведеною [[Кук, Стівен|Стівеном Куком]] в 1971-му році, задача SAT для булевих формул, записаних в [[Кон'юнктивна нормальна форма|кон'юнктивній нормальній формі]], є [[NP- повне завдання|NP- повною]]. Вимога про запис в кон'юнктивній формі є важливою, оскільки, наприклад, завдання SAT для формул, представлених в [[Диз'юнктивна нормальна форма|диз'юнктивній нормальній формі]], тривіально вирішується за лінійний час залежно від розміру запису формули.
 
==Точне формулювання==
Отримано з https://uk.wikipedia.org/wiki/Задача_здійсненності_булевих_формул