Гипотеза Кука — проблема ли?

[CherkasovMY]

«Фундамент теории NP-полных задач был заложен в работе С. Кука, опубликованной в 1971 г. <…> С. Кук доказал, что одна конкретная задача из NP, называемая задачей о выполнимости, обладает тем свойством, что всякая другая задача из класса NP может быть сведена к ней за полиномиальное время <…>. Таким образом, в некотором смысле задача о выполнимости — “самая трудная” в классе NP» [Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982, с. 27-28].
Вот только причисление задачи Выполнимость к классу NP-задач вызывает недоумение. Решение её состоит из двух этапов:

• во-первых, необходимо выяснить — не является ли рассматриваемое логическое выражение противоречивым. Если выражение представлено нормальной конъюнктивной формой, то, наличие какой-либо переменной в одной из скобок и её отрицания в другой, говорит о её противоречивости;
• во-вторых, в случае непротиворечивости исходного логического выражения, требуется найти набор переменных, при котором его значением будет “истина”.

Сделать это достаточно просто: по правилам логики, если все переменные логического выражения связаны связкой “или”, оно будет “истинным”, если хотя бы одна переменная принимает значение “истина”. Выражение, содержащее только связки “и”, будет “истинным”, если все переменные принимают значение “истина”. «… каждое сложное высказывание путем эквивалентного преобразования можно привести к известной нормальной форме…» [Гильберт Д, Аккерман В. Основы теоретической логики. 1947, с. 30]. Тогда, логическое выражение в нормальной конъюнктивной форме, будет “истинным”, если в каждой скобке хотя бы одна переменная имеет значение “истина”. В случае представления логического выражения в нормальной дизъюнктивной форме, то оно будет иметь значение “истина”, если, хотя бы в одной скобке, все переменные имеют значение “истина”.
Не меньшее удивление вызывает причисление к классу NP задачи о трёх красках (достаточно ли трёх красок, для раскраски заданной карты так, чтобы любые две соседние области были разного цвета?). Так, для раскраски любой области и прилежащих к ней областей трёх красок достаточно при четном количестве прилежащих областей. В противном случае необходимо уже четыре краски, следовательно, ответ будет отрицательным, если какая-нибудь внутренняя область граничит с нечетным количеством областей.
Свойство о достаточности четырёх красок для раскраски любой области и прилежащих к ней является доказательством теоремы о четырёх красках, т.к. ключевым словом здесь является “любая”, т.е. этим свойством обладает и сама область, и прилежащие к ней, и прилежащие к прилежащим, и т.д. Необходимо только соблюдать правила раскраски — двигаться по кругу и чередовать две краски.
Вопрос: Подвергает ли сомнению, изложенное выше, справедливость утверждения: Если существует полиномиальный алгоритм для какой-нибудь NP-полной задачи, то существуют полиномиальные алгоритмы для всех NP-полных задач» [Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. 1985, с. 352]?

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Помогите решить / разобраться (М)»
Причина переноса: пока сюда, дальше - в зависимости от поведения ТС

[Xaositect]

CherkasovMY в сообщении #1235415 писал(а):

во-первых, необходимо выяснить — не является ли рассматриваемое логическое выражение противоречивым. Если выражение представлено нормальной конъюнктивной формой, то, наличие какой-либо переменной в одной из скобок и её отрицания в другой, говорит о её противоречивости;

Нет, например $(x \vee y)(\bar{x} \vee z)$ не является противоречивой (истинна при $y = z = 1$).

CherkasovMY в сообщении #1235415 писал(а):

Не меньшее удивление вызывает причисление к классу NP задачи о трёх красках (достаточно ли трёх красок, для раскраски заданной карты так, чтобы любые две соседние области были разного цвета?). Так, для раскраски любой области и прилежащих к ней областей трёх красок достаточно при четном количестве прилежащих областей. В противном случае необходимо уже четыре краски, следовательно, ответ будет отрицательным, если какая-нибудь внутренняя область граничит с нечетным количеством областей.

Нет, например, вот у этой карты у каждой области три соседних, но ее можно покрасить в три цвета (и даже в два):
\begin{tikzpicture} \draw[fill=blue] (-1,-1)--(2,-1)--(2,2)--(-1,2)--cycle; \draw[fill=red] (0,0)--(1,0)--(0.5,0.7)--cycle; \draw[fill=green] (0,0)--(1,0)--(0.5,-0.7)--cycle; \draw[fill=blue] (0,0)--(-0.5,0.7)--(0.5,0.7)--cycle; \draw[fill=blue] (1,0)--(1.5,0.7)--(0.5,0.7)--cycle; \draw[fill=green] (-0.5,0.7)--(1.5,0.7)--(0.5,1.5)--cycle; \draw[fill=red] (0.5,-0.7)--(1.5,0.7)--(1.5,-0.7)--cycle; \draw[fill=red] (0.5,-0.7)--(-0.5,0.7)--(-0.5,-0.7)--cycle; \end{tikzpicture}

[CherkasovMY]

Выражение $(x \vee y)(\bar{x} \vee z)$ изначально содержит противоречие. Раскроем скобки и получим: $x\bar{x} \vee x z \vee y \bar{x} \vee yz$. Логика исключает из рассмотрения выражения, содержащие выражения типа «противоречие или истина». Видимо надо было говорить о проверке выражения на наличие в нем противоречивых частей.
По поводу картинки — нарушено основное требование: соприкасаться в одной точке могут не более трех областей.

[iifat]

CherkasovMY в сообщении #1235570 писал(а):

Логика исключает из рассмотрения выражения, содержащие выражения типа «противоречие или истина»

Это ж какой садист преподал вам такую логику?

[CherkasovMY]

Deggial в сообщении #1235420 писал(а):

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Помогите решить / разобраться (М)»
Причина переноса: пока сюда, дальше - в зависимости от поведения ТС

Можно ли, изменив название темы с "Гипотеза Кука — проблема ли?" (это ведь риторический вопрос), на "Гипотеза Кука проблемой не является", вернуть ея в раздел "Дискуссионные темы"?

[Deggial]

CherkasovMY в сообщении #1235576 писал(а):

Можно ли, изменив название темы с "Гипотеза Кука — проблема ли?" (это ведь риторический вопрос), на "Гипотеза Кука проблемой не является", вернуть ея в раздел "Дискуссионные темы"?

С таким изменением названия могу только в Карантин отправить с требованием изложить строгое доказательство этого ложного утверждения.

[Xaositect]

CherkasovMY в сообщении #1235570 писал(а):

Выражение $(x \vee y)(\bar{x} \vee z)$ изначально содержит противоречие. Раскроем скобки и получим: $x\bar{x} \vee x z \vee y \bar{x} \vee yz$. Логика исключает из рассмотрения выражения, содержащие выражения типа «противоречие или истина». Видимо надо было говорить о проверке выражения на наличие в нем противоречивых частей.

По какому учебнику Вы учили логику? Вообще-то такие утверждения встречаются сплошь и рядом, начиная от бытового "если будет хорошая погода, то буду делать то, а если нет - то что-нибудь другое". Это конъюнкция двух импликаций $(x \to y)(\bar{x} \to z)$, и она эквивалентна $(\bar{x} \vee y)(x \vee z)$.

CherkasovMY в сообщении #1235570 писал(а):

По поводу картинки — нарушено основное требование: соприкасаться в одной точке могут не более трех областей.

Тогда задача действительно простая, но если этого требования нет, то она NP-полная. Сейчас специально проверил Гэри-Джонсона, там этого требования нет.

[CherkasovMY]

По поводу противоречивых выражений. Ваше право — проверять ли выражение на противоречивость, не проверять ли. Суть задачи выполнимость заключается в нахождении значений логических переменных, входящих в какое-то логическое выражение, чтобы её значение стало истинным. Эта задача решается за полиномиальное время $O(n)$, львиная доля которого уходит на приведение исходного выражения к конъюнктивной или дизъюнктивной нормальной форме. Опираясь на правила использования логических операций и и или, найти значения некоторых переменных, вне зависимости от значений других, при которых выражение будет истинным — дело пяти минут (см. пункт во-вторых).

Цитата:

«Таким образом, если задача о выполнимости может быть решена за полиномиальное время, то и любая задача из класса NP полиномиально разрешима» [Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982, с. 27-28].]

Тогда получается, что для всех NP-полных задач существуют полиномиальные алгоритмы их решения? А это может означать только одно: класс NP-полных задач — пуст!

О задаче раскраски карт. Вот упоминание о необходимом условии:

Цитата:

«Не рассматриваются и случаи, когда четыре и более областей имеют общую точку» [Мир математики. Т. 25, с. 88].

Только суть дела не в этом.
При рассмотрении задачи о раскраске карт используют два понятия: прилежащие области (области, имеющие общую границу), соприкасающиеся области (области, имеющие общую точку). При решении задачи о достаточном количестве красок, необходимо эти понятия объединить в одно понятие: окружающие области. Тогда, взяв какую-нибудь область, окруженную другими областями, снаружи от её границ, на небольшом расстоянии от неё, провести замкнутую линию, охватывающую всю область. Подсчитаем количество окружающих областей, которые она пересекает. Любое натуральное число может быть либо четным, либо нечетным, следовательно, получим два варианта:

1. Рассматриваемую область окружает четное количество областей. Тогда, достаточно двух красок, чтобы их раскрасить, соблюдая условие несовпадения красок, плюс ещё одна краска для закрашивания самой области. Итого: достаточно трех красок.
2. Рассматриваемую область окружает нечетное количество областей. Тогда, достаточно трёх красок, чтобы их раскрасить, соблюдая условие несовпадения красок, плюс ещё одна краска для закрашивания самой области. Итого: достаточно четырех красок.

Основываясь на этих свойствах, сформулируем теорему:
Теорема о раскраске карт. Для закрашивания областей любой карты трёх красок достаточно, при условии, что все области, за исключением приграничных, окружены четным количеством областей. Если же хотя бы одна внутренняя область окружена нечетным количеством областей, то потребуется уже четыре краски.
Доказательство. См. изложенное выше.
Таким образом, задача о достаточном количестве красок при раскраске карт не имеет отношения к классу NP-полных задач.
Подобные рассуждения справедливы и для теории графов.

[Xaositect]

CherkasovMY в сообщении #1235872 писал(а):

По поводу противоречивых выражений. Ваше право — проверять ли выражение на противоречивость, не проверять ли. Суть задачи выполнимость заключается в нахождении значений логических переменных, входящих в какое-то логическое выражение, чтобы её значение стало истинным. Эта задача решается за полиномиальное время $O(n)$, львиная доля которого уходит на приведение исходного выражения к конъюнктивной или дизъюнктивной нормальной форме. Опираясь на правила использования логических операций и и или, найти значения некоторых переменных, вне зависимости от значений других, при которых выражение будет истинным — дело пяти минут (см. пункт во-вторых).

Покажите, пожалуйста, как Вы будете искать значения переменных для выражения

$$(x \vee u \vee v) (x \vee y \vee z) (y \vee \bar z \vee u) (y \vee \bar u \vee \bar v) (z \vee \bar u \vee v) (x \vee \bar y \vee \bar z) (\bar z \vee u \vee \bar v) (\bar y \vee \bar u \vee \bar v) (\bar y \vee z \vee \bar v) (\bar x \vee z \vee u) (\bar x \vee \bar z \vee v) (y \vee \bar z \vee \bar v)$$

Оно уже приведено к конъюнктивной нормальной форме.

CherkasovMY в сообщении #1235872 писал(а):

При рассмотрении задачи о раскраске карт используют два понятия: прилежащие области (области, имеющие общую границу), соприкасающиеся области (области, имеющие общую точку).

Вот именно. И задача будет NP-полной именно если учитывать только прилежащие области, если все окружающие области раскрашивать разными цветами, то задача простая. Но это две разные задачи, и я говорю про первую, а Вы - про вторую.

[mihaild]

CherkasovMY в сообщении #1235872 писал(а):

Тогда получается, что для всех NP-полных задач существуют полиномиальные алгоритмы их решения? А это может означать только одно: класс NP-полных задач — пуст!

Не значит, это значит что $\mathrm{P = NP = NP-complete}$.

[Iam]

CherkasovMY в сообщении #1235872 писал(а):

1. Рассматриваемую область окружает четное количество областей. Тогда, достаточно двух красок, чтобы их раскрасить, соблюдая условие несовпадения красок, плюс ещё одна краска для закрашивания самой области. Итого: достаточно трех красок.
.................................
Теорема о раскраске карт. Для закрашивания областей любой карты трёх красок достаточно, при условии, что все области, за исключением приграничных, окружены четным количеством областей. Если же хотя бы одна внутренняя область окружена нечетным количеством областей, то потребуется уже четыре краски.
Доказательство. См. изложенное выше.
Таким образом, задача о достаточном количестве красок при раскраске карт не имеет отношения к классу NP-полных задач.
Подобные рассуждения справедливы и для теории графов.

То, что Вы называете «доказательством» (теоремы о раскраске карт) на доказательство далеко не тянет. Попытайтесь что-нибудь покрасить и увидите его ошибочность.

[CherkasovMY]

Xaositect в сообщении #1235880 писал(а):

Покажите, пожалуйста, как Вы будете искать значения переменных для выражения

$$(x \vee u \vee v) (x \vee y \vee z) (y \vee \bar z \vee u) (y \vee \bar u \vee \bar v) (z \vee \bar u \vee v) (x \vee \bar y \vee \bar z) (\bar z \vee u \vee \bar v) (\bar y \vee \bar u \vee \bar v) (\bar y \vee z \vee \bar v) (\bar x \vee z \vee u) (\bar x \vee \bar z \vee v) (y \vee \bar z \vee \bar v)$$

Оно уже приведено к конъюнктивной нормальной форме.

Это выражение — противоречиво. Например, при $x=y=z=1$ выражение примет вид: $(\bar z \vee u \vee \bar v) (\bar y \vee \bar u \vee \bar v) (\bar x \vee \bar z \vee v) = (0 z \vee u \vee \bar v) (0 \vee \bar u \vee \bar v) (0 \vee 0 \vee v) = (u \vee \bar v) (\bar u \vee \bar v) (v)$. Тогда $v=1, u=1, (0 \vee 0)=1$.
Не усложняйте себе жизнь. Если хотите найти значения некоторого набора переменных, при которых выражение примет значение истина , используйте дизъюнктивную нормальную форму: противоречия вылезут в явном виде, а для нахождения значений переменных, достаточно рассмотреть какое-нибудь одно подскобочное выражение. Если же интересует значение ложь, то удобнее использовать конъюнктивную форму.

[Dmitriy40]

CherkasovMY в сообщении #1236172 писал(а):

Это выражение — противоречиво.

Это не так. Всего лишь комбинация $x=y=z=1$ не подходит, но это не значит что нет другой подходящей комбинации. Например $z=u=1, \, x=y=v=0$ обращает выражение в $1$.

[12d3]

CherkasovMY в сообщении #1236172 писал(а):

Не усложняйте себе жизнь.

Мы бы с удовольствием, но в задаче о выполнимости сказано, что входные данные совершенно не обязаны быть в ДНФ. Если входные данные только в ДНФ, то это совершенно другая задача, и она, как вы верно заметили, тривиальна.