NP-полнота, NP-полные задачи и булевы формулы

[Amicus Plato]

Что же такое 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 опять откладывается.

@темы: Алгоритмы, Искусственный интеллект, Поп-математика, Amicus Plato

Comments

[Sensile]

(на самом деле, можно обойтись и двумя, но это уже получится извращение).

А одной нельзя? (что-то мне такое припоминается то ли про стрелку Пирса, то ли штрих Шеффера.. или я ошибаюсь?)

[Amicus Plato]

Sensile
ммммм... Не помню...
А с отрицанием как быть? Они ж бинарные операции.

UPD. Ха!
Кстати да!
И штрих Шеффера и стрелка Пирса могут заменить отрицание!
Здорово!

[Гость]

ПОЛИНОМИАЛЬНОЕ РЕШЕНИЕ ЗАДАЧИ О КЛИКЕ:

clique-problem.narod.ru

[Гость]

Неполное обьяснение и немного не понятное, а на самом деле там все легко и просто

[Amicus Plato]

Гость
милости прошу: сообщество открыто всем. Объясните полнее и понятнее

[Aegypius Monachus]

А с отрицанием как быть? Они ж бинарные операции.
Можно обойтись двумя операциями. Варианты пар -
1 дизъюнкция и отрицание,
2 конъюнкция и отрицание,
3 конъюнкция и сумма по модулю 2,
4 дизъюнкция и сумма по модулю 2.
В случаях 3 и 4 отрицание заменяется сложением по модулю 2 с единицей. Без отрицания никуда.

Может быть понятие булевых формул проще показать на техническом устройстве?
Есть некий семисегментный индикатор. Каждый сегмент может находиться в 2-х состояниях (светиться или не светиться). Нужно, чтобы десятичное число от 0 до 9, представленное комбинацией нулей и елиниц (4-х булевых аргументов), могло быть представлено с помощью семисегментного индикатора в привычном нам виде.
Для каждого сегмента нужно построить булеву формулу от 4-х аргументов. Каждая булева формула - конструкция, которую согласно несложным правилам можно собрать из элементарных деталей (нарпимер конъюнкторов и инверторов, реализующих конъюнкцию и отрицание), реализующих булевы операции . Чем не детский конструктор? Вполне посильная задача для пытливых умов детского сада и младших классов.

[Amicus Plato]

Aegypius Monachus

Без отрицания никуда.

Однако же, без отрицания всё же "куда":
ru.wikipedia.org/wiki/Стрелка_Пирса

Насчет "технического устройства" — для технарей это, конечно, более понятно)) Но для гуманитариев, боюсь, нет...
Но вообще, это дело вкуса, как объяснять. Проблема в том, что при "дистанционном объяснении" обратная связь практически отсутствует, а без нее трудно...