У Онотоле о моем NP != P доказательстве. Надо добавить в него подробностей наверно.
Я про результаты (может и промежуточные) обсуждения моего доказательства после вот чего:
awas1952 16 мая 2014, 13:24:14
Поставил этот вопрос перед своими читателями1. Меня удивило в основном корректное отношение. Была пара придурков с "а, какая-то шмакодявка задачу тысячелетия мнит что решила, говно". Я на них посрал :) С остальными вежливо и с ( Read more... )
awas1952 16 мая 2014, 13:24:14
Поставил этот вопрос перед своими читателями1. Меня удивило в основном корректное отношение. Была пара придурков с "а, какая-то шмакодявка задачу тысячелетия мнит что решила, говно". Я на них посрал :) С остальными вежливо и с ( Read more... )
http://dmitgu.livejournal.com/76863.html
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.
Reply
Наш алгоритм-опровержение - назовем его Анти-МТ (на самом деле это будет семейство алгоритмов, как увидим) - будет содержать в своем составе алгоритм МТ (мы же предполагаем, что алгоритм МТ существует). В качестве аргумента для работы МТ будет подставлен сам алгоритм Анти-МТ. Да - это классический метод логиков для построения всяких опровержений разрешимости и т.п. и этот классический метод основан на том, что алгоритм в состоянии выдать свой собственный «исходный код». Если интересна техническая сторона, то вот у меня на сайте:
Теорема Геделя - эвристические рассуждения
там в качестве примера я строю мини-программу 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 привело к противоречию. Мы построили алгоритм, результат которого можно указать быстро, при том, что алгоритм МТ этого сделать не смог.
Теорема доказана.
Reply
Leave a comment