Что же такое NP-полные задачи?
О задачах из класса NP мы уже поговорили, но оказывается, среди них есть особенные. И таких особенных тоже не так уж мало.
NP-полные задачи — это класс задач, лежащих в классе NP,
к которым сводятся все задачи класса NP за полиномиальное время. То есть, если найдется быстрый алгоритм (полиномиальный) для решения
любой из NP-полных задач, то и любая задача из класса NP тоже может быть решена быстро!
Вот сейчас я прочитала в одном месте удивительную мысль. Не могу не процитировать:
Зачем программисту знать о NP-полных задачах? Если для некоторой задачи удается доказать ее NP-полноту, есть основания считать ее практически неразрешимой. В этом случае лучше потратить время на построение приближенного алгоритма, чем продолжать искать быстрый алгоритм, решающий ее точно.
(с)
"В принципе", всё так и есть. Но проблема P=(?)NP так и висит в воздухе. И доказать неравенство тоже ведь никто не может, не только равенство.
О проблеме равенства классов P и NP, надеюсь, я напишу в следующей записи (и тем самым завершу этот цикл), а сейчас перечислю NP-полные задачи (не все, конечно) — для иллюстрации того, что их ведь достаточно много! А стоит решить "быстро" одну, и к ее решению можно будет свести все остальные! Вот где простор для деятельности!
Первое, и основное, что надо знать: к NP-полным задачам принадлежит
задача о выполнимости булевых формул.
Я и в прошлый раз, перечисляя задачи класса NP, начинала список именно ею, и в этот раз опять. Сейчас расскажу, почему.
В прошлый раз я описывала эту задачу очень и очень коротко. Потому что всё-таки не представляю, как объяснить, что такое булевы формулы и их выполнимость, на пальцах.
Но делать нечего: похоже, без этого не обойтись.
Небольшой экскурс в теорию и историюИсторияБулевы формулы названы в честь английского математика и логика Джорджа Буля. Если я назову его одним из основателей математической логики, я нисколько не преувеличу. Булева алгебра, булева логика, булева функция — это не просто "в честь него", — это в прямом смысле его! Его изобретения. Порождения его ума.
А еще одним его "порождением" стала дочь Этель Лилиан Войнич. (Надеюсь, молодое поколение еще знает эту писательницу!) Остальные четыре его дочери (и жена) оставили след в точных науках (а вот одна в семье не без урода пошла в литературу).Что же такое булева формула?
Булева формула — это формула
логики высказываний. Логика высказываний — самая простая из всех логик. Говорят еще, что это классическая логика нулевого порядка.
Про нее я даже могу рассказать, не прибегая ни к каким ухищрениям.
Остановимся на основном определении. "Высказывание". Что это такое?
Под высказыванием понимают любое повествовательное предложение, о котором можно сказать, истинно оно или ложно.
Например
(с этого я каждый раз начинаю первое занятие по матлогике) какие из перечисленных предложений являются высказываниями?
0. Который час?
1. 2*2=4
2. 2*2=5
3. Лондон — столица Парижа.
4. Включите свет.
5. 2*х=8
6. a*b = b*a для любых a и b
Ответ:Ответ:
0. — нет.
1. — да. Истинное.
2. — да. Ложное.
3. — да. Ложное.
4. — нет.
5. — нет. (почему?)
6. — да. Истинное.Продолжение теорииС высказываниями разобрались. Их может быть бесконечно много, но их логические значения могут быть равны всего двум константам: "истина" или "ложь". Поэтому сами высказывания нас больше интересовать не будут — нам всё равно, что в них утверждается. Для нас важно только принимаемое ими значение. Истину мы будем записывать как "1", ложь — как "0".
Сами высказывания мы будем обозначать большими буквами: А, В, С, и т.д.
Кроме таких вот "всказывательных переменных" в булевой формуле используются логические связки.
Я расскажу только о трех из них, потому что без этих трех нам никак не обойтись (на самом деле, можно обойтись и двумя, но это уже получится извращение).
1. Логическое сложение, или дизъюнкция. Обозначается: ∨. Соответствует союзу "или".
Если:
F = А ∨ В, то F истинно, когда истинна хотя бы одна из двух переменных: А или В. F — ложно, тогда и только тогда, когда А и В ложны одновременно.
Переберем все возможные варианты значений переменных А и В:
А=1 В=1 ⇒ 1 ∨ 1 = 1
А=1 В=0 ⇒ 1 ∨ 0 = 1
А=0 В=1 ⇒ 0 ∨ 1 = 1
А=0 В=0 ⇒ 0 ∨ 0 = 0
Видно, что очень похоже на обычное сложение (просто как бы больше единицы у нас нет числа, поэтому 1+1=1)))
2. Логическое умножение или конъюнкция. Обозначается: ∧. Соответствует союзу "и".
Если:
F = А ∧ В, то F истинно, тогда и только тогда, когда истинны обе переменные: А и В. F — ложно, когда хотя бы одна из двух переменных А или В ложна.
Для конъюнкции выполняется:
А=1 В=1 ⇒ 1 ∧ 1 = 1
А=1 В=0 ⇒ 1 ∧ 0 = 0
А=0 В=1 ⇒ 0 ∧ 1 = 0
А=0 В=0 ⇒ 0 ∧ 0 = 0
А вот это самое что ни на есть умножение! Без всяких оговорок.
3. Логическое отрицание. Если операции дизъюнкции и конъюнкции бинарны (т.е. для них требуется две переменных), то для операции отрицания нужна всего одна — она унарна.
Не-А пишется как А с чертой вверху или еще как ¬ А.
Для отрицания выполняются следующие соотношения:
А=1 ⇒ ¬ А=0
А=0 ⇒ ¬ А=1
Кроме этих трех есть еще разные логические связки. Самая распространенная: импликация: "→".
Формула "А → В" читается (не совсем точно, но всё же): "если А, то В".
Еще есть эквиваленция, исключающее или, штрих Шеффера, стрелка Пирса, но на них мы сейчас останавливаться не будем.
Так вот, высказывательные переменные, соединенные логическими связками, и образуют формулы.
В свою очередь, сами формулы можно тоже объединять с помощью связок в более сложные формулы. Чтобы правильно определить порядок действий, конечно, нам еще понадобятся скобки.
Всё это вкупе мы и назовем булевой формулой.
Почему же именно выполнимость булевых формул так важна для нас, я уже напишу в следующий раз. Так что финальная запись про Р=(?)NP опять откладывается.