NP не равно P.
авторы: Виталий Коваль, Игорь Билан.
Электронная почта: mathbilan [at] gmail [dot] com.
Целью данного сообщения является доказательство того факта что NP не равно P.
Определение 0.1: граф
это неориентированый граф из
вершин.
Определение 0.2: максимальная клика графа
это клика
из
вершин. В нашем случае
вершин выбираются случайным образом и достраиваются до рёбер клики.
Определение 0.3:
это множество вершин графа
.
Определение 0.4:
это множество вершин клики
.
Определение 0.5:
это множество вершин клики
.
Лемма 0.6. В типичном случае граф
содержит клику
из
вершин если
. И в типичном случае если
то
. И в типичном случае если
то
.
Доказательство: В типичном случае граф из
вершин содержит клику из
вершин если
согласно [1].
И если математическое ожидание числа клик равно
то
мы получаем , если
и
мало мы получаем
математическое ожидание числа клик равно
.
Если
и
то мы имеем
математическое ожидание числа клик равно
.
Если
и
то мы имеем
математическое ожидание числа клик равно
.
Конец доказательства леммы.
Определение 0.7:
Случайная величина суть
.
Дисперсия
суть
.
Сигнал суть
.
Математическое ожидание
суть
.
Функция плотности вероятности
суть
.
Лемма 0.8
В типичном случае если число испытаний мало и
и
и
то мы не можем зафиксировать сигнал
.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Определение 0.9:
это множество рёбер графа
.
Определение 0.10:
это число операций алгоритмической машины.
Определение 0.11:
;
.
Лемма 0.12
;
;
;
;
;
мы имеем если
то
. И
применяя мемму 0.8
Доказательство леммы:
Если
и
то
; если
то
и
. Применяем мемму 0.8. Согласно [1] то мы имеем в графе из
вершин в типичном случае содержит клику
и
. Мы имеем вершины
в
вершин и
. То мы не можем зафиксировать сигнал
.
Конец доказательства.
Определение 0.13:
Граф
это неориентированный граф.
клики из
вершины графа
.
это ребра
если в
клики
соединены рёбрами если
(1) Если
и
и
и
то
минимальна.
(2) Если
и
и
то
больше.
(3) Если
и
и
то
больше.
Лемма 0.14
В лемме 0.12 аналогично заменяем
на
и мы также не можем зафиксировать сигнал
.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Рис.1 матрица смежности с
Рис.2 матрица смежности с
и
Определение 0.15:
.
.
Лемма 0.16
Расположение
показано на Рис.1.
.
Если
то заменим
на
в
. Если
мы не можем зафиксировать сигнал
.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Лемма 0.17
Расположение
показано на Рис.1.
.
Если
то заменим
на
в
. Если
мы не можем зафиксировать сигнал
.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Лемма 0.18
Расположение
показано на Рис.1.
.
Если
то заменим
на
в
. Если
мы не можем зафиксировать сигнал
.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Лемма 0.19
Расположение
показано на Рис.2.
и
и
.
Если
то заменим
на
в
. Если
мы не можем зафиксировать сигнал
. Если
мы не можем зафиксировать сигнал
. Если
мы не можем зафиксировать сигнал
.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Лемма 0.20
В лемме 0.19 аналогично заменяем
на
и мы также не можем зафиксировать сигнал
.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Лемма 0.21
В лемме 0.16, лемме 0.17, лемме 0.18, аналогично заменяем
на
мы также не можем зафиксировать сигнал
.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Определение 0.22
Граф
это граф
с переименованными вершинами.
Лемма 0.23
Шаг 1.
и
и
и
пробегает
Шаг 2. Меняя местами
и
в графе
получаем
Шаг 3. Если
то
.
Шаг 4. Переходим к шагу 1.
Мы также не можем зафиксировать сигнал
.
Доказательство:
.
.
. Используем лемму 0.8.
Конец доказательства леммы.
Лемма 0.24
В лемме 0.23, аналогично заменяем
на
то мы также не можем зафиксировать сигнал
.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Определение 0.25:
Граф
это неориентированный граф и
Лемма 0.26
Шаг 1.
и
и
и
пробегает
Шаг 2. Меняя местами
и
в графе
получаем
Шаг 3. Если
то
.
Шаг 4. Переходим к шагу 1.
Мы также не можем зафиксировать сигнал
.
Доказательство:
Если
то
.
Если
то
.
Если
то
.
Используем лемму 0.8.
Лемма 0.27
В лемме 0.26,аналогично заменяем
на
то мы также не можем зафиксировать сигнал
.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Определение 0.28:
Алгоритмическая машина J это
(1)
(2)IF
THEN
(3)
генерируется из
(4)
to
(5)
переменные для промежуточных вычислений.
(6)
;
;
(7)
on
.
Лемма 0.29
Алгоритмическая машина J полиномиально эквивалентна машине Тьюринга.
Доказательство:
Согласно [2], мы получаем
нейронной сети, и мы получаем машина Тьюринга
нейронной сети.
Конец доказательства леммы.
Лемма 0.30
Если задаче поиска клики свести к другой NP-полной проблеме то при обратном переходе мы приходим к лемме 0.26.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Лемма 0.31
Если мы не ищем максимум
то также не можем зафиксировать сигнал
.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Лемма 0.32
Если
то мы можем зафиксировать
вершин и сузить поиск до
вершин. Леммы остаются в силе.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Лемма 0.33
Мы можем использовать менее
объектов
.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства леммы.
Теорема 0.34
Используя леммы этой работы мы получаем, что NP не равно P.
Доказательство:
Доказательство предоставляется читателю.
Конец доказательства теоремы.
1.А.Д.Коршунова «Основные свойства случайных графов с большим числом вершин и рёбер» Успехи математических наук том 40 выпуск 1(241) 1985 год январь-февраль.
2. Саймон Хайкин Нейронные сети: полный курс 2-е издание Москва Санкт-Петербург Киев Вильямс 2006