NP-полнота Полиномиальная сводимость - Пусть Π1=(X1,Y1) и Π2=(X2,Y2) ― задачи распознавания. Будем говорить, что Π1 полиномиально сводится (по Карпу) к Π2 , если существует функция f : X1 X2 , вычислимая в полиномиальное время такая, что f(x)Y2 для всех xY1, и f(x)X2\Y2 для всех xX1\Y1 .
NP-полнота - Пусть U={u1, u2,…, uk}―множество булевых переменных.
- Под набором значений истинности на множестве U будем понимать функцию T: U {true, false}.
- Расширим T к множеству , полагая если и наоборот.
- Элементы множества L называются литералами.
Дизъюнкция - Дизъюнкцией над U называется множество литералов над U.
- Она представляет дизъюнкцию этих литералов и называется выполненной при некотором наборе значений истинности тогда и только тогда, когда при рассматриваемом наборе значений истинности хотя бы один из ее членов принимает значение “true”.
- Семейство (набор) Z дизъюнкций над U называется выполнимым в том и только том случае, если найдется некоторый набор значений истинности на множестве U, такой что выполнены все дизъюнкции из Z.
Задача «Выполнимость» - Условие. Задано множество переменных U и набор Z дизъюнкций.
- Вопрос. Является ли Z выполнимым?
Теорема Кука (1971) - Теорема 2.1
- Задача «Выполнимость» является NP-полной.
Do'stlaringiz bilan baham: |
