dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

NP не равно P. Мое «причесанное» доказательство задачи тысячелетия

Даю «причесанное» доказательство по результатам обсуждения в ЖЖ Онотоле. Первоначальное доказательство: NP != P. Я решил «задачу тысячелетия»? :). Первоначальное - заметно короче, но в нем пропущены некоторые очевидные для меня моменты. Тут, кстати видно, что когда чел «в теме», то он видит проблемы и решения в гораздо более «сжатом» виде и поэтому значительно проще обнаруживает то, что ему надо. Поэтому прежнее доказательство остается полезным - чтоб кратко и наглядно уловить ключевые идеи. Теперь перейдем к более подробному варианту.

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

Список проблем
Основная статья: Равенство классов P и NP

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

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

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

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

Например, рассмотрим умножение двух чисел (пример предложил khaibuloff в обсуждении моего доказательства, но вроде туда можно зайти только при регистрации на я.ру в клубе Наука и технология). Для простоты возьмем умножение числа на себя само (квадрат числа). Рассмотрим его для числа 999’999’999’999. Наш алгоритм - в соответствии с определением умножения - это сумма 999’999’999’999 чисел, каждое из которых равно 999’999’999’999. Длительность этого вычисления «в лоб» неполиномиально долгое (далее - просто «долгое»). Ну, действительно, потребуется больше действий, чем 10 в степени 12 (где 12 - число символов в 999999999999), то есть тут есть экспоненциальная зависимость от количества символов, которыми записан вычисляемый алгоритм (если у нас внутри алгоритма запись чисел - в духе привычного нам способа арабскими цифрами).

Но если мы применим стандартную формулу для умножения в столбик, то задача решается быстро. А есть и еще более быстрые способы расчета произведений, но и «в столбик» - расчет будет уже полиномиальный по времени исполнения.

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

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

Если у нас есть способ свести NP к P, то у нас должна быть и рассматриваемая нами МТ - потому что это тоже вариант «угадывания» быстрого решения, которое в принципе существует. Поэтому, наличие МТ - это необходимое условие того, чтобы NP = P (на самом деле оно и достаточное - уверен - но лень доказывать, потому что это тут не важно). И если МТ не существует, то и NP не может равняться P.

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

Так вот, мы исходим из предположения, что есть МТ с заданным свойством. А интересует нас только то свойство, что для алгоритмов из NP она дает результат из P. Более того, для нашего доказательства хватит всего лишь того, что МТ находит быстрые вычисления любого алгоритма Q из тех, для которых существует способ расчета за время, не более квадрата длины самого алгоритма Q (длины «текста» алгоритма Q). И вот тут должен быть полином pp, который задает предельное время получения результата алгоритмом МТ для подобного алгоритма Q. Потому что если такого полинома нет, то для любого полинома pp найдется такой алгоритм Q, который можно как-то вычислить за время не больше квадрата его длины, но который МТ не может «расколоть» в пределах времени, посчитанным полиномом pp. А в силу произвольности полинома pp расчет у МТ оказывается неполиномиальным даже для подмножества алгоритмов Q из класса NP.

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

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

Теорема Геделя - эвристические рассуждения
там в качестве примера я строю мини-программу 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

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

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

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

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

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

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


Замечания

Доказательство хорошо показывает причины невозможности свести NP к P: В имеющейся системе расчетов всегда есть некие бреши, и чтоб их отчасти «заткнуть» - надо выйдя за рамки готовой системы. И готового алгоритма для подобных «выходов» - нет, вообще говоря. Это аналог теорем о неполноте. Бреши всегда остаются. Собственно, и в своем доказательстве я использую аналогичные доказательствам из теорем о неполноте и неразрешимости приемы.

Притом «бреши» зачастую совершенно понятно как надо «затыкать», чтобы они  отвечали реальности. Например, утверждение «Это утверждение не доказывается в рамках следующих аксиом: <перечисление аксиом>». Это используется в доказательстве 2ой теоремы Гёделя и истинность данного утверждения достаточно очевидна. При этом теорию с «данным перечнем аксиом» можно расширить как данным утверждением в качестве новой аксиомы, так и ... его отрицанием. Но только первый вариант будет отвечать нормальной арифметике. А понять, что отвечает, а что нет - это вопрос без готовых алгоритмов решения, вообще говоря.

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

Новое в доказательстве теоремы о неравенстве P и NP то, что отсутствовать может не только возможность решить какой-то вопрос (в положительном или отрицательном смысле), но и что может отсутствовать достаточно быстрый способ решения, при том что само решение в принципе есть. Но это ведь изначально достаточно очевидно (если ты в теме вопросов вычислимости):

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

Поэтому я изначально - когда увидел вопрос о равенстве P и NP подумал, что тут просто доказать неравенство, но из-за более важных вопросов забыл об этом на несколько лет. И даже когда написал доказательство для себя - еще 4 года не публиковал его.

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

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

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.
  • 10 comments