dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Categories:

NP != P. Я решил «задачу тысячелетия»? :)


Отстрелу

садистских  матерей

посвящается.

Преамбула

[Нажмите чтобы прочитать. Личное, не про математику, а про посвящение и т.п.]

В июне прошлого (2013) года я уволился с прежней работы и повременил устраиваться на серьезную новую - надо было привести к некому устойчивому результату накопившиеся умственные дела. Что удалось сделать - можно посмотреть в моем ЖЖ за этот период, а основное - в Верхний ПСТО (о бессмертии :) от 2014/04, 15. А главным было понять причины моего детства с садистской падалью мамой (далее - СПМ) и тем, почему наше общество  на стороне этой мрази - защищая её (но не все люди на стороне этой нелюди). Кроме того, надо было остановить разрушение разума, который имел факты принуждения к спешке, насилия к себе со времен моего поганого детства, но не имел убедительных умственных контрдоводов.

Среди намеченных умственных дел была и одна из «Задач тысячелетия» - проблема Равенство классов P и NP.  Она будет рассмотрена ниже в «Амбуле». Сформулированное решение (по моему мнению, которое надо проверить, конечно) этой проблемы у меня было - я веду хронологию всяких нужных дел, идей и планов - с 06 августа 2010 г.  А вообще, как только я увидел эту проблему, то сразу был уверен, что знаю как решить (в конце 90-х, читая «Введение в Криптографию»), но сподобился сформулировать решение (?) только в 2010 году. Просто в основном меня занимали более важные - и я уверен в этом своем мнении - вопросы.

Тут фокус во влиянии этики на разум - разум является коллективным инструментом на самом деле, и если тебе не предоставляют условий, то это - обычно решающее основание для отказа от разума. Поэтому так трудно думать на темы находящиеся под запретом общества - например, о необходимости казнить садистских матерей. Наше поганое - в своем отношении к детям и разуму - общество не считает нужным предоставлять людям (детям особенно) условия для разума. Оно, видите ли, считает, что тех, кто ведет себя как фашист, кто просто нелюдь в отношении к разуму - особенно к разуму детей - что таких гнид не нужно убивать как бешеных собак! Оно - это «наше» общество - позволяет поганому садистскому бабью заявлять о своей «святости»! Что якобы эти животные «дают жизнь»! Мрази, в своей охреневшей заносчивости ставящие себе на уровне и выше Бога, уничтожающие разум и их - не отстреливают!

Собственно, с какого хрена мне было давать такому обществу ответы на интересующие его вопросы? Да пусть оно сдохнет - такое общество. И если ты не имеешь убедительных аргументов о том, к каким хреновым последствиям для общества ведет лояльность к СПМ и подобным гнидам, то ты попадешь под хор мразей: «Ты такой умный и решил проблему и имеешь за это ништяки только благодаря тому, что мама тебя хреачила и растаптывала». Так вот - сосите хрен у пожилого зайца. Я ее ненавидел, ненавижу и делаю вопреки тому, что «вдалбливала» эта гнида и оправдывали вы - хор мразей. И это «вопреки» должно было стоить мне жизни - но лучше рисковать, чем соглашаться с «нашим» гребаным, поганым и предавшим меня - обществом.

В общем - понятно, почему «проблему тысячелетия» я отложил на потом. Никакая это не проблема тысячелетия, на самом деле, а вот что проблема - так это почему технообщество подыхает: стареет и либо заканчивает свое существование в трясине потреблятства, либо упиваясь оправданием садистских родительских мразей. Ура, ура - ответ был найден: 1. Жизнь - исключение. Разум отменяет его для людей, 2. Второй принцип защиты жизни.

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

Ну, конечно все эти важные открытия никто ни фига не видит, зато все прыгают вокруг «проблем тысячелетия». Ок. Значит, если дать всем этим скачущим «не москалям» ответ на какой-то «важный» (для них) вопрос, то можно и указать цену и затолкать в глотку хору мразей, воспевающих садистских родаков - их садизм. И вообще приблизиться к отстрелу садистских матерей - которые ничуть не лучше нацистских надзирателей в лагерях смерти.

Нет гарантий, что я не допустил какую-то ошибку в доказательстве, но вариант с NP != P самый потенциально сильный из имеющихся у меня для подхода к решения важных - на мой взгляд - общественных задач. Если он сорвется - в запасе есть и другие - более традиционные подходы. Да и деньги уже заканчиваются (на нынешней работе фиг знает когда заплатят долг по зарплате - если заплатят) - надо доводить до результата (какой бы он ни был) отложенное «на закуску» умственное дело и искать новую работу - либо уж менять жизнь - если доказательство корректно.

Вообще ошибка в математике (особенно в принципиальных сложных вопросах) - очень обычное дело - куда более обычное, чем обнаружение правильного решения. Да вот у той же проблемы Равенство классов P и NP полно было попыток доказательства, оказавшихся неудачными. По предыдущей ссылке есть раздел Примечания, где указана ссылка на перечень попыток - The P-versus-NP page. Кстати, не читал - с иностранным языком у меня туго. Одна из указанных там попыток в 2010 меня сначала напрягла - типа опередил кто-то, но оказалось, что меня это не пугает и я быстро успокоился - потому что меня интересуют более важные вопросы, а какой использовать инструмент для их достижения (решение «задачи тысячелетия» или иной способ) - вопрос второстепенный.

Да, если я ошибся в своем доказательстве утверждения NP != P, то наши маньяки, ненавидящие разум и не понимающие, как это все работает, начнут кидаться дерьмом, за неимением ничего иного у себя в головах. Ну, это пофиг. А что я высказал свое отношение к нашему обществу - о его поганом злобном предательстве детей и потакании садистскому бабью - так это ничего не добавило к тому, что я высказывал раньше и никогда не скрывал.

Еще кстати, вспомнил забавный эпик фейл в решении математической проблемы :) Бертран Рассел (кажется он с кем-то еще) написали книгу, где выводили все нужное из нескольких примитивных постулатов. И все было чудно, но им указали, что все получилось из противоречивого «множества всех множеств».И большой труд и большое время на этот труд пошли насмарку. Ндя, это было в крутые время в математике, пока Гёдель не открыл свое доказательство о невозможности системы доказать свою истинность (2я теорема Гёделя) - в неформальном виде. Собственно - в вопросах, родившихся в то фантастическое время я как раз неплохо разбираюсь и решение проблемы NP != P я даю (?) на основе методов, весьма типичных в вопросах разрешимости, вычислимости и логики. И решение - если это решение - получается удивительно коротким и - смею думать - простым.

Итак, перейдем к

«Амбула»

Смотрим Википедию - Задачи тысячелетия (до строки - многоточия):

Список проблем

Основная статья: Равенство классов P и NP

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

...

Ответ такой: Они не равны. То есть:

NP != P

Доказательство (Полторы страницы А4).

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

Например, алгоритм расчета суммы арифметической прогрессии - если складывать «в лоб» - неполиномиально долгий (далее - просто «долгий»). Чтоб сложить числа от 1 до 1’000’000’000’000 простым суммированием - потребуется экспоненциальное количество действий от 13 (число цифр в 1’000’000’000’000). Но если мы применим стандартную формулу для вычисления суммы арифметической прогрессии, то задача решается быстро.

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

Ну, частью «ключа» является еще доказательство этой быстрой формулы расчета. Но если бы у нас была истинная МТ, то сертифинатом был бы МТ с подставленным туда в качестве аргумента проверяемым алгоритмом. И такая конструкция позволяла бы быстро узнать, какой результат работы этого подставленного алгоритма и равен ли он предложенному для проверки числу. Если подставленный алгоритм в принципе имеет формулу для быстрого расчета.

Такое вот пояснение про ключи и проверки применительно к тому подходу, который применяю тут я. Все что написано в Википедии сводится - как видим - к быстрому расчету тех алгоритмов, для которых вообще существует быстрый расчет. 

Все дальнейшие рассуждения про МТ применимы к любому универсальному способу выполнения аналогичных действий. Это связано с «тезисом Чёрча». (ну, он утверждает, что все способы вычислений эквивалентны алгоритмам, грубо говоря, это признают математики, но это не предмет доказательства).

Так вот, мы исходим из предположения, что есть МТ с заданным свойством.

А теперь построим алгоритм-опровержение - классическим - для вычислимости и логики - способом.

Наш алгоритм-опровержение - назовем его Анти-МТ - будет содержать в своем составе алгоритм МТ (мы же предполагаем, что алгоритм МТ существует). В качестве аргумента для работы МТ будет подставлен сам алгоритм Анти-МТ. Да - это классический метод логиков для построения всяких опровержений разрешимости и т.п. и этот классический метод основан на том, что алгоритм в состоянии выдать свой собственный «исходный код». Если интересна техническая сторона, то вот у меня на сайте:

Теорема Геделя - эвристические рассуждения

там в качестве примера я строю мини-программу dolly на VBA (язык программирования, пригодный для Windows Word), которая выдает свой собственный текст. А вот эта программа:

Sub dolly(): x = ": Selection.InsertAfter (" + Chr(34) + "Sub dolly(): x = " + Chr(34) + " + Chr(34) + Replace(x, Chr(34), Chr(34) + " + Chr(34) + " + Chr(34) + " + Chr(34) + " + Chr(34)) + Chr(34) + x): End Sub": Selection.InsertAfter ("Sub dolly(): x = " + Chr(34) + Replace(x, Chr(34), Chr(34) + " + Chr(34) + " + Chr(34)) + Chr(34) + x): End Sub

Теперь наш Анти-МТ запускает внутри себя МТ и смотит, как этот самы МТ пытается рассчитать результат работы Анти-МТ. И если этот МТ выдаст за полиномиальное время результат 1, то наш Анти-МТ выдаст 0, а если за полиномиальное время этот самый МТ выдаст НЕ 1, то Анти-МТ «назло» МТ выдаст 1. Ну, а если МТ ничего не выдаст за полиномиальное время, то через долгое-долгое время наш Анти-МТ выдаст, например 2..

Как видим, наш МТ заведомо не может «расколоть» Анти-МТ за полиномиальное время потому, что сам Анти-МТ построен как опровержения метода МТ (каким бы этот метод ни был). В то же время у нас есть совершенно точное знание, каким будет результат работы Анти-МТ при корректном МТ - Анти-МТ выдаст 2. И «ключом» («сертификатом») для этого знания является сама структура построения Анти-МТ. Мы его так построили, что знаем, какой в итоге будет результат.

Ну, не обязательно будет "например 2", может быть любое число - его может подставить дядя Вася, а не мы, но по структуре функции мы всегда можем быстро понять, какой у нее будет результат. То есть - быстрый способ ее вычисления есть, но МТ его найти не может.

Таким образом, предположение, что существует алгоритм МТ, сводящий класс NP к классу P привел к противоречию. Мы построили алгоритм, результат которого можно указать быстро, при том, что алгоритм МТ этого сделать не смог.

Теорема доказана.

Гы... Где мой миллион долларов? ))))))

Tags: NP≠P дискуссии, Вычислимость и логика, ЖЖвЖЖ _обычное_, ЖЖвЖЖ математика, Мои открытия
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments