Задача здійсненності булевих формул
проблема визначення того, чи можна зробити булеву формулу істинною / З Вікіпедії, безкоштовно encyclopedia
Шановний Wikiwand AI, Давайте зробимо це простіше, відповівши на ключові запитання:
Чи можете ви надати найпопулярніші факти та статистику про Задача здійсненності бульових формул?
Підсумуйте цю статтю для 10-річної дитини
Зада́ча здійсне́нності бу́левих фо́рмул (SAT, від англ. satisfiability) — важлива для теорії обчислювальної складності алгоритмічна задача.
Об'єктом задачі SAT є булева формула, що складається тільки з назв змінних, дужок і операцій (І)
(АБО) і
(НІ).
Задача полягає в наступному: чи можна призначити усім змінним, що трапляються у формулі, значення хибність і істина так, щоб формула стала істинною.
Згідно з теоремою Кука, доведеною Стівеном Куком в 1971-му році, задача SAT для булевих формул, записаних в кон'юнктивній нормальній формі, є NP-повною. Вимога про запис у кон'юнктивній формі є важливою, оскільки, наприклад, для формул, представлених в диз'юнктивній нормальній формі, задача SAT тривіально вирішується за лінійний час від розміру запису формули.