2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В раздел Пургаторий будут перемещены спорные темы (преимущественно псевдонаучного характера), относительно которых администрация приняла решение о нецелесообразности продолжения дискуссии.
Причинами такого решения могут быть, в частности: безграмотность, бессодержательность или псевдонаучный характер темы, нарушение автором принципов ведения дискуссии, принятых на форуме.
Права на добавление сообщений имеют только Модераторы и Заслуженные участники форума.



Начать новую тему Ответить на тему
 
 NP не равно P
Сообщение09.12.2014, 12:46 


24/04/14
33
NP не равно P.
авторы: Виталий Коваль, Игорь Билан.
Электронная почта: mathbilan [at] gmail [dot] com.
Целью данного сообщения является доказательство того факта что NP не равно P.
Определение 0.1: граф $G$ это неориентированый граф из $n$ вершин.
Определение 0.2: максимальная клика графа $G$ это клика $C$ из $2\log_2n$ вершин. В нашем случае $2\log_2n$ вершин выбираются случайным образом и достраиваются до рёбер клики.
Определение 0.3:$V(G)$ это множество вершин графа $ G $.
Определение 0.4:$V(C)$ это множество вершин клики $ C $.
Определение 0.5:$V(F)$ это множество вершин клики $ F $.
Лемма 0.6. В типичном случае граф $ G $ содержит клику $F$ из $d$ вершин если $2(\log_2n-\log_2\log_2n)-1<d<2(\log_2n-\log_2\log_2n)+4$. И в типичном случае если $2(\log_2n)>d>2(\log_2n-\log_2\log_2n)+4$ то $F \in C$ . И в типичном случае если $2(\log_2n)<d$ то $F \notin G$ .


Доказательство: В типичном случае граф из $ V(G)\setminus V(C) $ вершин содержит клику из $d$ вершин если $2(\log_2n-\log_2\log_2n)-1<d<2(\log_2n-\log_2\log_2n)+4$ согласно [1].
И если математическое ожидание числа клик равно $ \binom{n}{r}2^{-\binom{r}{2}}$
то $ r = |V(F)|$ мы получаем , если $ |V(F)\cap V(C)|\sim k $ и $k$ мало мы получаем
математическое ожидание числа клик равно $  \binom{n}{r-k}2^{-\binom{r-k}{2}}\binom{2\log_2 n}{k}2^{-(r-k)k}\to 0$.

Если $ |V(F)\cap V(C)|\sim k $ и $k\sim \log_2n$ то мы имеем
математическое ожидание числа клик равно $  \binom{n}{r-k}2^{-\binom{r-k}{2}}\binom{2\log_2 n}{k}2^{-(r-k)k}\to 0$.
Если $ |V(F)\cap V(C)|\sim k $ и $k\sim 2 \log_2n$ то мы имеем
математическое ожидание числа клик равно $  \binom{n}{r-k}2^{-\binom{r-k}{2}}\binom{2\log_2 n}{k}2^{-k2\log_2n}\to 0$.
Конец доказательства леммы.
Определение 0.7:
Случайная величина суть $ X $.
Дисперсия $X$ суть $D(X)$.
Сигнал суть $S$.
Математическое ожидание $X$ суть $E(X)$.
Функция плотности вероятности $X$ суть $f(x)$.
Лемма 0.8
В типичном случае если число испытаний мало и $S=o(\sqrt{D(X)})$ и $f(x)\nearrow \colon x< E(X)$ и $f(x)\searrow \colon x> E(X)$ то мы не можем зафиксировать сигнал $S$.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.

Определение 0.9:
$H^1(G)$ это множество рёбер графа $G$.
Определение 0.10:
$T$ это число операций алгоритмической машины.
$T=n^m<n^{\log_2\log_2n}$
Определение 0.11:
$v \in V(G)$;
$H_1(v)=\{\eta \colon (v,\eta)\in H^1(G)\}$.
Лемма 0.12
$\eta_1 \in H_1(v)$ ;
$\eta_2 \in (H_1(v)\cap H_1(\eta_1))$;
$\eta_3 \in (H_1(v)\cap H_1(\eta_1)\cap H_1(\eta_2))$;
$\eta_4 \in (H_1(v)\cap H_1(\eta_1)\cap H_1(\eta_2)\cap H_1(\eta_3))\ldots$;
$\eta_i \in (H_1(v)\cap H_1(\eta_1)\cap H_1(\eta_2)\ldots \cap H_1(\eta_{i-1}))$;
мы имеем если $i<\log_2n/2$ то $T>n^{\log_2n/2}$. И $S=o(\sqrt{D(X)})$ применяя мемму 0.8
Доказательство леммы:
Если $X=|(H_1(v)\cap H_1(\eta_1)\cap H_1(\eta_2)\ldots \cap H_1(\eta_{i-1}))|$ и $S=2\log_2n$ то $S=o(\sqrt{D(X)})$; если $i<\log_2n/2$ то $X\sim n/2^{\log_2n/2}\sim \sqrt{n}$ и $D(X)\sim pq\sqrt{\sqrt{X}} ;q=p=1/2$ $\Rightarrow$ $S=o(\sqrt{D(X)})$. Применяем мемму 0.8. Согласно [1] то мы имеем в графе из $(H_1(v)\cap H_1(\eta_1)\cap H_1(\eta_2)\ldots \cap H_1(\eta_{i-1})) \sim \sqrt{n}$ вершин в типичном случае содержит клику $F$ и $V(F)\sim 2(\log_2\sqrt{n}-\log_2\log_2\sqrt{n})-1$. Мы имеем вершины $C$ в $\sqrt{n}$ вершин и $T=n^{\log_2\log_2n}$ $\Rightarrow$ $(2\log_2n/n)^{a}\sqrt{n}^aT$ $S=a$ $\Rightarrow$ $a=2\log_2\log_2n$. То мы не можем зафиксировать сигнал $S$.
Конец доказательства.
Определение 0.13:
Граф $ G_1 $ это неориентированный граф.
$V(G_1)=\{$клики из $\log_2\log_2n$ вершины графа $G  \}$.
$(\alpha_{b_1},\beta_{b_2})$ это ребра $G_1$ если в $G$ клики $\alpha_{b_1},\beta_{b_2}$ соединены рёбрами если $\Rightarrow$
(1) Если $\alpha_{b_1},\beta_{b_2}\in G_1  $ и $V(\alpha_{b_1})\cap V(\beta_{b_2})=\emptyset$ и $\forall v_1 \in V(\alpha_{b_1})$ и $\forall v_1 \in V(\beta_{b_2})$ $\Rightarrow$ $ (v_1,v_2) \in H^1(G) $ то $D(X)$ минимальна.
(2) Если $\alpha_{b_1},\beta_{b_2}\in G_1  $ и $\forall v_1 \in V(\alpha_{b_1})$ и $\forall v_1 \in V(\beta_{b_2})$ $\Rightarrow$ $ (v_1,v_2) \in H^1(G) $ то $D(X)$ больше.
(3) Если $\alpha_{b_1},\beta_{b_2}\in G_1  $ и $\exists v_1 \in V(\alpha_{b_1})$ и $\exists v_1 \in V(\beta_{b_2})$ $\Rightarrow$ $ (v_1,v_2) \in H^1(G) $ то $D(X)$ больше.
Лемма 0.14
В лемме 0.12 аналогично заменяем $G$ на $G_1$ и мы также не можем зафиксировать сигнал $S$.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.


Изображение Рис.1 матрица смежности с $Y_1,Y_2,Y_3$


Изображение Рис.2 матрица смежности с $Y$ и $u$



Определение 0.15:
$Y \subseteq V(G)*V(G)$.
$Y^1=|\{Y\cap H^1(G) \}|$.
Лемма 0.16
Расположение $Y_1,Y_2,Y_3$ показано на Рис.1. $Y_3\subseteq Y_2$.
Если $Y^1_1>Y^1_3 $ то заменим $Y_1$ на $Y_3$ в $Y_2$. Если $|V(Y_1)|<\sqrt{n}$ мы не можем зафиксировать сигнал $S$.

Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.

Лемма 0.17
Расположение $Y_1,Y_2,Y_3$ показано на Рис.1. $Y_3\subseteq Y_2$.
Если $Y^1_1>Y^1_3 $ то заменим $Y_1$ на $Y_3$ в $Y_2$. Если $\sqrt{n}<|V(Y_1)|<n/5$ мы не можем зафиксировать сигнал $S$.

Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.

Лемма 0.18
Расположение $Y_1,Y_2,Y_3$ показано на Рис.1. $Y_3\subseteq Y_2$.
Если $Y^1_1>Y^1_3 $ то заменим $Y_1$ на $Y_3$ в $Y_2$. Если $|V(Y_1)| \sim n$ мы не можем зафиксировать сигнал $S$.

Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.

Лемма 0.19
Расположение $Y$ показано на Рис.2. $Z_1\subseteq V(G)$ и $Z_2\subseteq V(G)$ и $|Z_1|=|Z_2|$.
Если $Y^1(Z_1)>Y^1(Z_2) $ то заменим $Z_1$ на $Z_2$ в $Y$. Если $u \sim n$ мы не можем зафиксировать сигнал $S$. Если $\sqrt{n}<u<n/5$ мы не можем зафиксировать сигнал $S$. Если $u<\sqrt{n}$ мы не можем зафиксировать сигнал $S$.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Лемма 0.20
В лемме 0.19 аналогично заменяем $G$ на $G_1$ и мы также не можем зафиксировать сигнал $S$.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.

Лемма 0.21
В лемме 0.16, лемме 0.17, лемме 0.18, аналогично заменяем $G$ на $G_1$ мы также не можем зафиксировать сигнал $S$.

Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.

Определение 0.22
Граф $ G_3 $ это граф $ G $ с переименованными вершинами.


Лемма 0.23
Шаг 1. $Z_1\subseteq V(G_3)$ и $Z_2\subseteq V(G_3)$ и $|Z_1|=|Z_2|$ и $Z_1,Z_2$ пробегает $V(G_3)$
Шаг 2. Меняя местами $Z_1$ и $Z_2$ в графе $G_3$ получаем $G^1_3$
Шаг 3. Если $|H^1(G)\cap H^1(G_3)|<|H^1(G)\cap H^1(G^1_3)|$ то $G_3:=G^1_3$.
Шаг 4. Переходим к шагу 1.
Мы также не можем зафиксировать сигнал $S$.
Доказательство:
$D(X) \sim (n/2)pq; p=q=1/2$. $S=2\log_2n$. $S=o(\sqrt{D(X)})$. Используем лемму 0.8.
Конец доказательства леммы.

Лемма 0.24
В лемме 0.23, аналогично заменяем $G$ на $G_1$ то мы также не можем зафиксировать сигнал $S$.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Определение 0.25:
Граф $ G_2 $ это неориентированный граф и $G_2 \ne G $
Лемма 0.26
Шаг 1. $Z_1\subseteq V(G_2)$ и $Z_2\subseteq V(G_2)$ и $|Z_1|=|Z_2|$ и $Z_1,Z_2$ пробегает $V(G_2)$
Шаг 2. Меняя местами $Z_1$ и $Z_2$ в графе $G_2$ получаем $G^1_2$
Шаг 3. Если $|H^1(G)\cap H^1(G_2)|<|H^1(G)\cap H^1(G^1_2)|$ то $G_2:=G^1_2$.
Шаг 4. Переходим к шагу 1.
Мы также не можем зафиксировать сигнал $S$.
Доказательство:
Если $|H^1(G)\cap H^1(G_2)\cap (V(G)*Z_i)|<\sqrt{n}$ то $S=o(\sqrt{D(X)})$.
Если $|H^1(G)\cap H^1(G_2)\cap (V(G)*Z_i)|>\sqrt{n}$ то $S=o(\sqrt{D(X)})$.
Если $|H^1(G)\cap H^1(G_2)\cap (V(G)*Z_i)|\sim n$ то $S=o(\sqrt{D(X)})$.
Используем лемму 0.8.
Лемма 0.27
В лемме 0.26,аналогично заменяем $G$ на $G_1$ то мы также не можем зафиксировать сигнал $S$.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.


Определение 0.28:
Алгоритмическая машина J это
(1) $Y_1, Y_2, \ldots ,Y_{n^m}$
(2)IF $Y_i>Y_j$ THEN $\ldots$
(3)$Y_w$ генерируется из $V(Y_i)$
(4)$V(Y_i)$ to $\cap \, \setminus \,\cup $
(5) $R_i$ переменные для промежуточных вычислений.
(6) $>\, <\, =\, IF\, R_i<R_j \, THEN \,\ldots $; $\,IF\, R_i>R_j \, THEN \,\ldots \,$; $\,IF\, R_i=R_j \, THEN \,\ldots \,$
(7) $ *\, , /\, , +\, , -\,$ on $R_i$.
Лемма 0.29
Алгоритмическая машина J полиномиально эквивалентна машине Тьюринга.
Доказательство:
Согласно [2], мы получаем $J \sim NARX$ нейронной сети, и мы получаем машина Тьюринга $\sim NARX$ нейронной сети.

Конец доказательства леммы.
Лемма 0.30
Если задаче поиска клики свести к другой NP-полной проблеме то при обратном переходе мы приходим к лемме 0.26.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Лемма 0.31
Если мы не ищем максимум $R_i$ то также не можем зафиксировать сигнал $S$.

Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.

Лемма 0.32
Если $T=\log_2\log_2n$ то мы можем зафиксировать $\log_2\log_2n$ вершин и сузить поиск до $\sqrt{n}$ вершин. Леммы остаются в силе.

Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Лемма 0.33
Мы можем использовать менее $T<n^{\log_2\log_2n}$ объектов $Y_l$.

Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.

Теорема 0.34
Используя леммы этой работы мы получаем, что NP не равно P.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства теоремы.




1.А.Д.Коршунова «Основные свойства случайных графов с большим числом вершин и рёбер» Успехи математических наук том 40 выпуск 1(241) 1985 год январь-февраль.
2. Саймон Хайкин Нейронные сети: полный курс 2-е издание Москва Санкт-Петербург Киев Вильямс 2006

 Профиль  
                  
 
 Re: NP не равно P
Сообщение09.12.2014, 15:22 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Зачем так многабукафф?
Можно куда проще, например:
Код:
Теорема 0.0
NP не равно P.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства теоремы.

:evil:

 Профиль  
                  
 
 Re: NP не равно P
Сообщение19.10.2015, 12:13 


24/04/14
33
статья около полугода проходила рецензирование в трудах американского математического общества и теперь ее статус следующий:
Article Status: Reviewing
Your paper is being handled by an editor.
что это точно значит, не знаю, но может быть для кого то это будет полезно.
редактор --Sergei K Suslov

 Профиль  
                  
 
 Re: NP не равно P
Сообщение20.10.2015, 05:19 


12/07/15
01/11/24
3276
г. Чехов
bilan в сообщении #1064324 писал(а):
Article Status: Reviewing
Your paper is being handled by an editor.

Статус статьи: рассматривается
Твоя бумага обрабатывается редактором :D

 Профиль  
                  
 
 Re: NP не равно P
Сообщение20.10.2015, 05:26 
Заслуженный участник
Аватара пользователя


21/12/05
5931
Новосибирск
bilan в сообщении #1064324 писал(а):
Your paper is being handled by an editor

Редактор безуспешно ищет желающих отрецензировать.
Ваша статья обрабатывается редактором.

 Профиль  
                  
 
 Re: NP не равно P
Сообщение26.10.2015, 12:23 


23/01/15
8
Попытался прочитать :D . Споткнулся уже на определении 0.2. Обычно под максимальной кликой понимается клика которая не содержится ни в какой другой клике большего размера. Что же определяется здесь, от меня совершенно ускользает.
Далее, лемма 0.7. Что означает "в типичном случае"?
Определение 0.7. Хотелось бы все же определение, а не просто перечисление непонятно чего.
Ну и лемма 0.8, что означает "зафиксировать сигнал S"?

Учитывая, что практически во всех леммах мы "не можем зафиксировать сигнал", дальше пока читать не стал до прояснения :D .

 Профиль  
                  
 
 Re: NP не равно P
Сообщение26.10.2015, 14:02 


24/04/14
33
определение 0.2 станет понятнее если проработать статью
bilan писал(а):
А.Д.Коршунова «Основные свойства случайных графов с большим числом вершин и рёбер» Успехи математических наук том 40 выпуск 1(241) 1985 год январь-февраль.

ответ на
m(Ax) писал(а):
Далее, лемма 0.7. Что означает "в типичном случае"?
содержится в той же статье А.Д.Коршунова :-)
определение 0.7 это скорее соглашение об обозначениях :-)
ответ на
m(Ax) писал(а):
Ну и лемма 0.8, что означает "зафиксировать сигнал S"?

в условиях леммы 0.8 мы не можем отличить $X+S$ и $X$ при одном испытании. :-)

-- 26.10.2015, 13:06 --

точнее если число испытаний мало

 Профиль  
                  
 
 Posted automatically
Сообщение26.10.2015, 18:34 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
Причина переноса: не оформлены цитаты

bilan
Освойте тег quote, а также кнопки Изображение и Изображение, исправьте цитаты в последнем сообщении.
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

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

 Профиль  
                  
 
 Re: NP не равно P
Сообщение29.01.2016, 11:15 


24/04/14
33
пришел ответ:

Dear Prof. Bilan,

This message concerns the manuscript

NP is not P
by Vitaliy Vladimirovich Koval and Igor Urevich Bilan

submitted to Proceedings of the AMS.

Unfortunately, we cannot accept it for publication. It does not meet the standards that we require. Most results are not proved anyway and the proofs are left to the reader.

We apologize for taking such a long time to make this decision. The editor originally in charge of your submission had health problems and was unable to perform his duties for PAMS.

Sincerely,

Walter Van Assche
Editor of Proceedings of the American Mathematical Society

 Профиль  
                  
 
 Re: NP не равно P
Сообщение29.01.2016, 11:35 


14/01/11
3017
Жалко редактора. :-(

 Профиль  
                  
 
 Re: NP не равно P
Сообщение30.01.2016, 06:18 
Заслуженный участник
Аватара пользователя


21/12/05
5931
Новосибирск
Долго редактор думал, даже занемог, бедняга, но ответ дал толерантный.

 Профиль  
                  
 
 Re: NP не равно P
Сообщение30.01.2016, 15:30 


23/02/12
3335
bot в сообщении #1095219 писал(а):
Долго редактор думал, даже занемог, бедняга, но ответ дал толерантный.

Учитесь! :-)

 Профиль  
                  
 
 Re: NP не равно P
Сообщение06.02.2016, 13:55 
Аватара пользователя


27/02/09

416
Мегаполис
bot в сообщении #1095219 писал(а):
Долго редактор думал, даже занемог, бедняга, но ответ дал толерантный.


долго оценивал и потом решил, что был болен, так как не мог так долго оценивать

и потом редактора осенило - "так и по формальным свойствам же доказательства нет" - что и ответил

-- Сб фев 06, 2016 15:12:05 --

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

Так?

 Профиль  
                  
 
 Posted automatically
Сообщение06.02.2016, 19:37 


20/03/14
12041
 i  Тема перемещена из форума «Дискуссионные темы (М)» в форум «Пургаторий (М)»
Будучи полностью солидарными с редактором, мы приносим свои извинения за столь долгое время, которое понадобилось на принятие настолько очевидного решения.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group