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

Матеріал з Вікіпедії — вільної енциклопедії.

Зада́ча здійсни́мості бу́льових фо́рмул (SAT) — задача розпізнавання образів, важлива для теорії обчислювальної складності.

Об'єктом задачи SAT є булева формула, що складається тільки з імен змінних, дужок і операцій (І), (АБО) і (HІ). Задача полягає в наступному: чи можна призначити всім змінним, що зустрічаються у формулі, значення НЕВІРНО і ВІРНО так, щоб формула стала істинною.

Згідно теоремі Кука, доведеною Стивеном Куком в 1971-му році, проблема SAT є NP-повною.

[ред.] Дивіться також

Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні джерела. Матеріал без джерел може бути підданний сумніву та вилучений.

Це незавершена стаття з математики. Ви можете допомогти проекту, виправивши або дописавши її.