доказательство NP ≠ P в Eastern European Scientific Journal

[maxal]

Для любителей искать ошибки:

V. V. Koval, I. Y. Bilan, NP Not Equal to P, Eastern European Scientific Journal, October 2013, pp. 115-122.
(не смотря на английское название, сама статья на русском)

[venco]

А стоит? Журнал какой-то... платный для писателей.

[maxal]

Я же сказал, что для любителей -- тех, кто находит поиск ошибок в чужих "доказательствах" увлекательным.

[Urnwestek]

venco в сообщении #799870 писал(а):

Журнал какой-то... платный для писателей.

(Оффтоп)

Особенно дизайн обложки клёвый. (:

[Xaositect]

Статьи в журнале, который при редактуре не исправляет "Дерихле" на "Дирихле", поиска ошибок не заслуживают.

[bilan]

Здравствуйте, коллеги!
дано понятное доказательство того факта, что NP не равно Р
30.10.2013 года опубликован №5/2013 журнала “Eastern European Scientific Journal”. Ссылка на журнал в интернете [реклама удалена] по ссылке Journal и далее Eastern European Scientific Journal October 2013 или [реклама удалена] с.114

название статьи: "NP not equal to P"
с уважением Билан И.
P.S. статья на русском языке, только аннотация и название на английском





Авторы:
Виталий В. Коваль, кандидат технических наук, Украина, Черкассы

Игорь Ю. Билан, Украина, Черкассы


NP не равно P.
Ключевые слова: NP-полная задача, клика, граф.
Аннотация: в данной статье авторы доказывают не совпадение классов NP-полных задач, и класса P-задач. Доказательство производится с использованием дизъюнктивных нормальных форм, для задачи поиска ответа на вопрос, содержит ли граф клику заданного размера. Точной оценки трудоемкости данной NP-полной задачи статья не содержит, доказывается только ее не полиномиальность.



Рассмотрим, для доказательства, проблему ответа на вопрос содержит ли неориентированный граф $G$ из $n$ вершин клику размером $\sqrt[2]{n}$ .
В качестве входных данных рассмотрим матрицу смежности $A$.
Так как граф неориентированный, то достаточно рассматривать часть матрицы смежности над главной диагональю,(так как матрица $A$ симметрична).
В качестве алгоритмической модели рассмотрим L-машину, которая содержит ячейки с входными данными (нули или единицы матрицы смежности $A$), промежуточные переменные, и переменную ответа, которая равна $1$, если клика размером $\sqrt[2]{n}$ содержится в графе, и $0$ , если клика размером не содержится в графе. При этом L-машина выполняет следующие действия: $AND, OR$, и $NOT$.
Лемма 1. Можно полиномиальным образом преобразовать любой алгоритм L-машины, так, что отрицания берутся только от ячеек с входными данными (то есть только от элементов матрицы $A$ , а не от промежуточных переменных).
Доказательство леммы1.
Доказательство проведем по индукции, от числа шагов вычислений L-машины.
Базис индукции: Для 1. У нас одновременно со значением каждой ячейки матрицы смежности $A$ содержится также ее отрицание.
Предположение индукции: пусть для $n$-го шага вычислений у нас вместе со значением каждой промежуточной переменной содержится также ее отрицание, и при этом мы брали отрицание только от переменных-начальных-данных.
Шаг индукции: на $n+1$ шаге вместе с $d=a OR b$, вычисляем одновременно
$NOT d= NOT a AND NOT b$, используя закон де Моргана, а
вместе с $d=a AND b$, вычисляем одновременно
$NOT d= NOT a OR NOT b$, также используя закон де Моргана.
Таким образом, так как у нас имелись все отрицания всех переменных, на $n$-м шаге, мы получаем отрицания всех переменных на$n+1$ шаге не используя оператора $NOT$ , при этом сложность алгоритма возрастает не более чем в $2$ раза.
Что и требовалось доказать.
Конец доказательства леммы 1.
Лемма 2.
Все промежуточные переменные, и переменную ответа, можно представить в виде ДНФ, от переменных-начальных-данных и отрицаний переменных-начальных-данных.
Доказательство леммы 2.
Доказательство проведем по индукции.
Базис индукции: Для 1. У нас каждая переменная-начальное-данное или его отрицание, являются ДНФ.
Предположение индукции: пусть для $n$-го шага вычислений у нас каждая переменная представлена в виде ДНФ.
Шаг индукции: на $n+1$ шаге у нас происходит вычисление $d=a OR b$, тогда ДНФ переменной $d$ образуется из ДНФ переменных $a$ ,и $b$ по следующему правилу: ДНФ переменной $d$ содержит каждый конъюнкт как ДНФ переменной $a$, так и ДНФ переменной $b$, при этом совпадающие конъюнкты включаются только один раз. При этом на всех возможных наборах переменных-начальных-данных $d=1$ тогда и только тогда когда или $a$ или $b$ или одновременно $a$ и $b$ равно $1$.
Пусть $d=a AND b$, тогда конъюнкты ДНФ образуются по следующему правилу: каждый конъюнкт ДНФ $d$ должен быть произведением каких то конъюнктов одного из ДНФ $a$, а другого из ДНФ $b$.
При этом перебираются все возможные конъюнкты ДНФ $a$, и ДНФ $b$. В таком случае только когда $a$ и одновременно $b$ равны $1$, а значит и в ДНФ $a$ есть конъюнкт равный $1$, и в ДНФ $b$ есть конъюнкт равный $1$, тогда их произведение этих конъюнктов в ДНФ $d$ даст в результате $1$.
Что и требовалось доказать.
Конец доказательства леммы 2.
Лемма 3.
Вид ДНФ переменной ответа.
Доказательство леммы 3.
ДНФ переменной ответа содержит все конъюнкты следующего вида и только их:
Это конъюнкты, каждый из которых содержит проверку на существование клики размером $\sqrt[2]{n}$ ,то есть утверждение переменных матрицы смежности, которые вместе образуют все ребра какой то клики. При этом для каждой клики, группа конъюнктов, в которой содержатся утверждение переменных матрицы смежности, которые вместе образуют все ребра этой клики, остальные переменные конъюнктов перебирают все возможные комбинации остальных переменных, не входящих в клику. Это потому, что из за того, что на любом графе, содержащем какую то клику, ДНФ ответа должен принять значение $1$, при любых значениях переменных не входящих в клику.
То есть для любого набора значений переменных не входящих в клику, в ДНФ ответа, должен содержаться конъюнкт, который на этом наборе переменных $= 1$, при условии, что все ребра отвечающие за клику $=1$.
ЗАМЕЧАНИЕ: некоторые переменные, не отвечающие за клику могут отсутствовать в конъюнктах ДНФ ответа, при это м понятно, их значения могут быть любые, если конечно этим конъюнктом выполняется проверка на клику.
Конец доказательства леммы 3.
Введем некоторые обозначения, необходимые для доказательства:
Обозначение 1: часть конъюнкта, проверяющую на утверждение ребер клики и только их назовем кликоподобной частью.
Обозначение 2: дополнение до кликоподобной части на тех же переменных (отвечающих только за клику) назовем основной частью.
Обозначение 3: часть конъюнкта содержащее все кроме кликоподобной или основной части назовем дополнительной частью.
Обозначение 4: $\tilde{1_p}$ это на множестве $p$ переменных ДНФ которая состоит из всех возможных конъюнктов на $p$ переменных без возможных упрощений. В данном случае мы имеем $2^{|p|}$ конъюнктов в ДНФ $\tilde{1_p}$ . Замечание: в каждом конъюнкте $\tilde{1_p}$ содержится $|p|$ переменных.
Обозначение 5:$|x|_p$ это ДНФ на множестве переменных $p$ содержащее $x$ разных конъюнктов, каждый из которых состоит из $p$ переменных.
Обозначение 6: $|<x|_p$ это ДНФ на множестве переменных $p$ содержащее менее $x$ разных конъюнктов, каждый из которых состоит из $p$ переменных.
Обозначение 7: $|>x|_p$ это ДНФ на множестве переменных $p$ содержащее более $x$ разных конъюнктов, каждый из которых состоит из $p$ переменных.
Обозначение 8: $A_p$ это множество разных конъюнктов, на $p$ переменных каждый из которых состоит из $p$ переменных.
Обозначение 9: $A_p \dot{-} B_p$ это множество конъюнктов $A_p$ без конъюнктов $B_p$ .
Обозначение 10: $A_p \dot{*} B_c$ при $p \bigcap c=\varnothing$ это ДНФ состоящее из конъюнктов, каждый из которых есть произведение конъюнкта из $A_p $ на конъюнкт из $B_c$ во всех возможных комбинациях.
Обозначение 11: $A_p \dot{*} B_c$ при $p \bigcap c \neq \varnothing$ это ДНФ состоящее из конъюнктов, каждый из которых есть произведение конъюнкта из $A_p $ на конъюнкт из $B_c$ во всех возможных комбинациях.(аналог $AND$)
Обозначение 12: $ \frac{\tilde{1_p}}{n^h}=|2^{p-h \log_2 n}|_p$
Обозначение 13: $A_p \dot{+} B_p$ это ДНФ состоящее из конъюнктов, каждый из которых содержится либо в $A_p $ либо в $B_p $ .(аналог $ OR$)
Обозначение 14: $A_p \dot{*} B_p=C_p$ при этом в ДНФ $C_p $ состоит из конъюнктов, каждый из которых содержится как в $A_p $ так и в $B_p $ , эти конъюнкты назовем «живыми» в отличии от «мертвых», которые содержатся или только в $A_p $ или только в $B_p $ , и не содержатся в $C_p $ .

Теорема:
для построения ДНФ ответа требуется экспоненциальное число ходов L-машины.
Начало доказательства.
Проведем доказательство от противного.
Пусть мы построили ДНФ ответа. Покажем, что его нельзя получить за полиномиальное время, меньшее чем $ n^h$ .
Пусть мы преобразовывали ДНФ ответа $ n^h$ операциями $ OR$.
При этом согласно принципу Дерихле, у нас найдется переменная $W$, конъюнкты которой отвечают за проверку не менее чем за $\frac{C_n^{\sqrt[2]{n}}}{n^h}$ клик. Дополнительные части, в переменной $W$, для каждой клики также содержат не менее чем $\frac {2^{\frac{n(n-1)}{2}-\frac{\sqrt[2]{n}(\sqrt[2]{n}-1)}{2}}}{n^h}$ вариантов согласно тому же принципу Дерихле, мы можем выбрать такую переменную $W$. Если также содержатся конъюнкты более перечисленных, то это не меняет общности.
В результате переменная $W$ представляется в таком виде:


Рис. 1
Далее, у нас есть два пути: первый – это с помощью $OR$ разложить так, чтобы у каждой клики в ДНФ, была общая с остальными кликами часть.
И вынести эту общую часть за скобки, с помощью $AND$.

Рис. 2 .
Тут красное – это общая часть, зеленое – индивидуальная часть каждой клики.
Даже для разложения на $\frac{\sqrt[2]{n}}{2}$ требуется $C_n^{\frac{\sqrt[2]{n}}{2}}$ что больше $n^h$.
Второй случай: когда у нас в $W$ содержатся две клики которые полностью не совпадают.
В таком случае мы должны рассматривать с помощью $AND$ образование $W$, при этом отслеживая деление на «мертвые» и «живые» конъюнкты.
Рассмотрим $A_p \dot{*} B_p=C_p$ .
«мертвые» конъюнкты должны содержаться как в $A_p$ , так и в $B_p$ . Иначе мы получим $A_p$ или $B_p$ равное $C_p$ , и никакого прогресса у нас не будет.
Если в $A_p$ и $B_p$ будет просто содержаться по $\frac{1}{2}$ от недостающих до $\tilde{1_{граф}}$ различных конъюнктов, то мы получим дерево, листьев у которого столько, сколько недостающих до $\tilde{1_{\text{граф}}}$ конъюнктов у $W$ . Что более чем $n^h$.
Рассмотрим, куда, и как можно добавить «мертвые» конъюнкты, чтобы строго соблюдалось число «живых» конъюнктов, если у нас в $W$ , или в $C_p$ содержатся две клики, у которых любые два ребра различны.
Первый случай:

Рис 3
$A_p=1,2$; $B_p=3,4$; $C_p=5,6$;
$A_p \dot{*} B_p=C_p$ , тут происходит попытка вписать «мертвые» конъюнкты в $A_p$ за счет основной части $\text{клики}_1$, и $\text{клики}_2$ и в за счет основной части $\text{клики}_1$, и $\text{клики}_2$.
Получаем, что у нас равенство соблюдаться не будет, из за того, что возникнут лишние «живые» конъюнкты.
Рассмотрим:
$2 AND 3$, а также $1 AND 4$;
В качестве «живых» конъюнктов возникают следующая группа конъюнктов:
рассмотрим например $2 AND 3$,зеленая часть основной части $\text{клики}_1$, общая дополнительная часть $2$, и $3$, и зеленая основная часть $\text{клики}_2$; выпадает красная кликоподобная часть $\text{клики}_1$ и красная кликоподобная часть $\text{клики}_2$; это не укладывается в набор «живых» конъюнктов $C_p$, так как две части различных клик никогда не дадут одной клики (тем более две части совершенно не совпадающих клик, не будут покрыты одной кликой, что в результате даст нам лишние «живые» конъюнкты)
Второй случай: то есть, на основании выше рассмотренного, у нас такая ситуация:
Выносить за скобки общую часть клик мы не можем, потому, что получается более чем полиномиальная сложность.
Одновременно добавить в виде произведения основные части двух не совпадающих клик тоже не можем, получаются лишние живые конъюнкты.
Мертвые конъюнкты разбивать, на две группы и переводить их в живые с помощью операции $AND$, мы тоже не можем, т.к. получается более чем полиномиальная трудоемкость.
Остается единственный выход: рассматривать мертвые конъюнкты из единственной основной части, и при этом, мертвые конъюнкты выводить из игры следующим образом, чтобы не скатиться в более чем экспоненциальную трудоемкость:



Рис 4.
При этом у нас основная часть $\text{клики}_1$, переходит из мертвых конъюнктов в живые, за время $n$ , так как у нас листьев у дерева $AND$ будет столько сколько переменных, так как на каждом шаге, у нас из мертвых в живые переходит в $2^a$ конъюнктов более чем на предыдущем шаге, где $A$ -- число переменных, от которых берется $\tilde{1_a}$ различных значения, которые умножаются на все предыдущие.
Однако и в этом, последнем случае, нас ожидает разочарование, из за того, что мы двигаясь в обратном направлении (то есть от полученной $1\text{-цы}$) не получим желаемый результат. На каждом шаге мы теряем информацию о других кликах, и чтобы эту информацию сохранить, нам будет необходимо раскладывать с помощью $OR$ экспоненциальное число раз.
Потеря информации представлена на следующем рисунке 5:



Рис 5.
«Туда» мы получаем достаточное количество «мертвых» конъюнктов, «обратно» мы получаем чистую кликоподобную часть, но при этом мы теряем информацию об остальных кликоподобных частях.
То есть мы рассмотрели все случаи, и в каждом из них получили более чем полиномиальную трудоемкость.
Примечание: то что в дополнительных частях может содержаться в $n^h$ меньше конъюнктов, не влияет на ход доказательства, а лишь усложняет выкладки, поэтому мы это не рассматривали.
Конец доказательства.

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
Причина переноса: текст доказательства не приведен в теме

bilan
Приведите весь текст доказательства прямо в теме. Необходимо, чтобы он удовлетворял правилам дискуссионного раздела.
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[Deggial]

Тема перемещена из форума «Карантин» в форум «Дискуссионные темы (М)»
Возвращено

bilan в сообщении #853989 писал(а):

принципу Дерихле

на правах рекламы

[Nemiroff]

topic83329.html
topic83532.html

Да начнётся битва!

[vicvolf]

Бедный Дерихле! Вы и в статье его так величаете?
http://ru.wikipedia.org/wiki/%D0%94%D0% ... 1%91%D0%BD

[bilan]

кажется, и в статье Дирихле у меня Дерихле, тут уже ничего не поделаешь :(
с уваженеим Билан И.

[maxal]

Темы объединены

[bilan]

Глубоко уважаемые колеги!
если вопрос "скользкий" -- пишите в личку!
гарантирую, что отвечу всем, и без ехидства!
к тому же остается открытым вопрос точной оценки трудоемкости решения данной проблемы Клика -- это будет лично Ваш результат, которій как мне кажется довольно легко выводится из представленного материала, а это -- результат мирового уровня!
с глубоким уважением Билан И.

[whitefox]

Чтобы из Вашей теоремы следовал сабж, нужно ещё показать, что для всякой полиномиальной задачи, соответствующая ДНФ имеет полиномиальную же сложность.

[bilan]

Глубоко уважаемый whitefox!

полиномиальная сложность для полиномиальной задачи следует из того, что она решается L-машиной за полиномиальное время.
поэтому ее ДНФ строится L-машиной за полиномиальное время.
известно, что L-машина полиномиально еквивалентна той же машине Тьюринга.

с глубоким уважением Билан И.

-- 30.04.2014, 10:03 --

кроме того, размер ДНФ для полиномиальной задачи может быть експоненциальным, а строится она, все же за полиномиальное время. тут дело в структуре ДНФ.
с глубоким уважением Билан И.