По поводу противоречивых выражений. Ваше право — проверять ли выражение на противоречивость, не проверять ли. Суть задачи
выполнимость заключается в нахождении значений логических переменных, входящих в какое-то логическое выражение, чтобы её значение стало
истинным. Эта задача решается за полиномиальное время
, львиная доля которого уходит на приведение исходного выражения к конъюнктивной или дизъюнктивной нормальной форме. Опираясь на правила использования логических операций
и и
или, найти значения некоторых переменных, вне зависимости от значений других, при которых выражение будет
истинным — дело пяти минут (см. пункт
во-вторых).
Цитата:
«Таким образом, если задача о выполнимости может быть решена за полиномиальное время, то и любая задача из класса NP полиномиально разрешима» [Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982, с. 27-28].]
Тогда получается, что для всех NP-полных задач существуют полиномиальные алгоритмы их решения? А это может означать только одно: класс NP-полных задач — пуст!
О
задаче раскраски карт. Вот упоминание о необходимом условии:
Цитата:
«Не рассматриваются и случаи, когда четыре и более областей имеют общую точку» [Мир математики. Т. 25, с. 88].
Только суть дела не в этом.
При рассмотрении задачи о раскраске карт используют два понятия:
прилежащие области (области, имеющие общую границу),
соприкасающиеся области (области, имеющие общую точку). При решении задачи о достаточном количестве красок, необходимо эти понятия объединить в одно понятие:
окружающие области. Тогда, взяв какую-нибудь область,
окруженную другими областями, снаружи от её границ, на небольшом расстоянии от неё, провести замкнутую линию, охватывающую всю область. Подсчитаем количество
окружающих областей, которые она пересекает. Любое натуральное число может быть либо четным, либо нечетным, следовательно, получим два варианта:
1. Рассматриваемую область окружает четное количество областей. Тогда, достаточно двух красок, чтобы их раскрасить, соблюдая условие несовпадения красок, плюс ещё одна краска для закрашивания самой области. Итого: достаточно трех красок.
2. Рассматриваемую область окружает нечетное количество областей. Тогда, достаточно трёх красок, чтобы их раскрасить, соблюдая условие несовпадения красок, плюс ещё одна краска для закрашивания самой области. Итого: достаточно четырех красок.
Основываясь на этих свойствах, сформулируем теорему:
Теорема о раскраске карт. Для закрашивания областей любой карты трёх красок достаточно, при условии, что все области, за исключением приграничных, окружены четным количеством областей. Если же хотя бы одна внутренняя область окружена нечетным количеством областей, то потребуется уже четыре краски.Доказательство. См. изложенное выше.
Таким образом, задача о достаточном количестве красок при раскраске карт не имеет отношения к классу NP-полных задач.
Подобные рассуждения справедливы и для теории графов.