«Фундамент теории NP-полных задач был заложен в работе С. Кука, опубликованной в 1971 г. <…> С. Кук доказал, что одна конкретная задача из NP, называемая задачей о выполнимости, обладает тем свойством, что всякая другая задача из класса NP может быть сведена к ней за полиномиальное время <…>. Таким образом, в некотором смысле задача о выполнимости – «самая трудная» в классе NP» [1, с. 27-28].
Вот только причисление задачи ВЫПОЛНИМОСТЬ к классу NP-задач вызывает недоумение. Решение её состоит из двух этапов:
– во-первых, необходимо выяснить – не является ли рассматриваемое логическое выражение противоречивым. Если выражение представлено нормальной конъюнктивной формой, то, наличие какой-либо переменной в одной из скобок и её отрицания в другой, говорит о его противоречивости;
– во-вторых, в случае непротиворечивости исходного логического выражения, требуется найти набор переменных, при котором его значением будет ИСТИНА. Сделать это достаточно просто: по правилам логики, если все переменные логического выражения связаны связкой ИЛИ, то оно будет ИСТИННЫМ, если хотя бы одна переменная принимает значение ИСТИНА. Выражение, содержащее только связки И, будет ИСТИННЫМ, если все переменные принимают значение ИСТИНА. Следовательно, логическое выражение в нормальной конъюнктивной форме будет ИСТИННЫМ, если в каждой скобке хотя бы одна переменная имеет значение ИСТИНА.
Не меньшее удивление вызывает причисление к классу NP задачи о трёх красках (достаточно ли трёх красок, для раскраски заданной карты так, чтобы любые две соседние области были разного цвета). Так, для раскраски любой области и прилежащих к ней областей трёх красок достаточно при четном количестве прилежащих областей. В противном случае необходимо уже четыре краски. Следовательно, ответ будет отрицательным, если какая-нибудь внутренняя область граничит с нечетным количеством областей.
Свойство о достаточности четырёх красок для раскраски любой области и прилежащих к ней является доказательством теоремы о четырёх красках, т.к. ключевым словом здесь является ЛЮБАЯ, т.е. этим свойством обладает и сама область, и прилежащие к ней, и прилежащие к прилежащим, и т.д. Только необходимо соблюдать правила раскраски – двигаться по кругу и чередовать две краски.