Задача P/NP

Автор темы sukhikh 
ОбъявленияПоследний пост
ОбъявлениеМГУ и Яндекс объявили об открытии на мехмате специализации по анализу данных и машинному обучению24.08.2021 00:17
ОбъявлениеPostdoc: Stochastics and algorithmics behind network problems (Netherlands)08.10.2021 08:36
ОбъявлениеГранты для студентов и аспирантов мехмата и физфака МГУ на обучение в магистратуре Кембриджа 2022/202314.10.2021 12:28
22.08.2021 16:38
Задача P/NP
Теорема.
Превосходит ли класс NP класс P, или они равны друг другу?
Доказательство.
Пусть имеется система из n элементов. Установим связи элементов в этой системе. Алгоритм по установлению связи элементов ”1” и ”2” состоит из t1 шагов. Алгоритм по установлению связи элементов “1” и ”3” состоит из t2 шагов. (t1 и t2 – сравнимые между собой числа, поэтому просто будем обозначать t). Связь элемента “1” с каждым другим элементом в паре устанавливается за (n-1)t шагов. Связь элемента ”2” с каждым другим элементом в паре, начиная с элемента ”3”, устанавливается за (n-2)t шагов. Итого, связь каждого из n элементов попарно с другим элементом системы устанавливается за (1+2+3+….+(n-1))t = (n-1)nt/2 шагов.
Влияет ли элемент ”3” на взаимодействие элементов ”1” и ”2”? Алгоритм выяснения этого вопроса состоит из f шагов (f и t – сравнимые между собой числа, поэтому просто будем обозначать f через t). Влияние каждого из других элементов на взаимодействие элементов ”1” и ”2” устанавливается за (n-2)t шагов. Влияние каждого из других элементов на взаимодействие элемента ”1” с одним из каждых (n-1) элементов устанавливается за (n-1)(n-2)t шагов. (Влияние элемента ”3” на взаимодействие элементов ”1” и ”2” не равно влиянию элемента ”2” на взаимодействие элементов ”1” и ”3”). Итого, влияние каждого из других элементов на взаимодействие пары элементов в системе из n элементов устанавливается за n(n-1)(n-2)t шагов.
Рассматривая влияние каждого из других элементов на взаимодействие любых трёх элементов системы, мы придём к выводу, что такое влияние устанавливается за n(n-1)(n-2)(n-3)t шагов.
Аналогично, влияние каждого из других элементов на взаимодействие любых m элементов в системе из n элементов устанавливается за n(n-1)(n-2)….(n-m)t шагов. (m возрастает до (n-1) ).
Итого, для установления всех связей между элементами в системе из n элементов требуется
(n(n-1)/2 + n(n-1)(n-2) +….+ n(n-1)(n-2)….(n-m)….(n-(n-1)))t =
(n!/2(n-2)! + n!/(n-3)! +….+n!/(n-m-1)! +….+ n!)t шагов.
Этот алгоритм превосходит не только класс P, но и класс E.
Если в системе установлены k связей, то их проверка будет состоять из kt шагов.
Таким образом, класс NP превосходит класс P.
22.08.2021 22:18
496
Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать?[

Если это истинное решение задачи то отыскав решение мы проверили его.

Думаю надо настроит арифметику истинно потом другие науки.



Редактировалось 1 раз(а). Последний 23.08.2021 03:19.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти