NP≠P. Док-во от противного-контрпример алгоритмов из NP

[dmitgu]

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

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

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

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

Доказательство (Две с небольшим страницы А4. С ссылками и короткая версия - в моем ЖЖ [реклама удалена]).

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

Например, рассмотрим умножение двух чисел. Для простоты возьмем умножение числа на себя само (квадрат числа). Рассмотрим его для числа 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 привело к противоречию. Мы построили алгоритмы, результат которых можно указать быстро, при том, что алгоритм МТ этого, вообще говоря, сделать не может.

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

[warlock66613]

Так где контрпример-то? Слов много, а описания NP-полной задачи в этих словах не угадывается...

[dmitgu]

warlock66613 в сообщении #865294 писал(а):

Так где контрпример-то? Слов много, а описания NP-полной задачи в этих словах не угадывается...

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

"Фишка" доказательства в том, что если бы такой метод был, то он сам и является таким решением (пригодным для проверки) для каждой конкретной такой задачи. Потому что он и результат выдаст быстро и - в силу своей истинности - он выдаст правильный результат. И я рассматриваю действие этого метода на множестве всех тех алгоритмов, для которых можно каким-то образом "предвидеть" результат их работы за полиномиальное время. И представлен этот метод на этом множестве алгоритмом МТ. Наверно, множество таких алгоритмов - это NP-полная задача, но это не имеет значения для доказательства и нет необходимости это выяснять.

А контрпример - это Анти-МТ. Алгоритм, который дает иной результат, чем тот, который он "должен" выдать по "мнению" МТ.
Притом:
1. Анти-МТ работает неполиномиально долго
2. Какой результат работы будет у Анти-МТ можно узнать за полиномиальное время

[warlock66613]

Итак, есть некоторая общерекурсивная функция $AntiMT: \mathbb N \to \mathbb N$, и соответствующая задача ($AntiMT$), которая состоит в том, чтобы вычислить значение этой функции зная значение агрумента. Утверждается, что $AntiMT \in \mathbb {NP}$, но $AntiMT \notin \mathbb P$. Так или нет?

[dmitgu]

warlock66613 в сообщении #865742 писал(а):

Итак, есть некоторая общерекурсивная функция $AntiMT: \mathbb N \to \mathbb N$, и соответствующая задача ($AntiMT$), которая состоит в том, чтобы вычислить значение этой функции зная значение агрумента. Утверждается, что $AntiMT \in \mathbb {NP}$, но $AntiMT \notin \mathbb P$. Так или нет?

Так, но после одного уточнения. Доведу Ваш первый вопрос до требования к доказательству:

"Наличие способа проверки сертификата есть способ ограничить задачи рамками NP, а если этого нет, то от МТ потребуется (возможно) работать с набором задач, выходящим за рамки NP."

Но ограничить набор задач тут легко (вроде бы...). Придется еще добавить нюанс (как это сделать, чтоб старый текст сохранился и новый появился?):

Надо после абзаца с началом:
Ну, частью «ключа» является еще доказательство этой быстрой формулы расчета....

Поставить абзац:
Важный момент! Все-таки множеством интересующих нас алгоритмов будем считать те алгоритмы, для которых есть доказательство полиномиальной длины способа их быстрого расчета. Проверка доказательства имеет полиномиальную скорость (близкую к линейной), поэтому полиномиальность времени проверки при полиномиальном (от размера самого доказываемого утверждения) размере доказательства сохраняется. Тут нюанс в том, что при разных наборах аксиом будут разные выборки и если не задать отбор по доказательствам, то выборка может выйти в некоторых местах за пределы NP. Поэтому мы задаем и набор аксиом. Но он должен быть достаточно выразительным, чтоб алгоритмы могли анализировать свои тексты.

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

После абзаца с началом:
Но у всего семейства Анти-МТ одинаковая структура и достаточно «глянуть» на конкретный экземпляр Анти-МТ, чтобы увидеть, что он из того самого семейства...

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

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

Замечание:
После приведенных уточнений становится понятна причина невозможности МТ:
Наличие полиномиального доказательства для произвольного алгоритма, который можно быстро посчитать и который имеет такое док-во... Но! МТ подменяет собой тогда любое такое доказательство, а они могут быть сколь угодно большими. Вот тут, похоже, и находится противоречие, делающее невозможным существование. Ведь во все больших утверждения содержатся (в некоторых из них) все новые смыслы, которые изначально ограниченный МТ уже не в силах в себе содержать.

[warlock66613]

dmitgu в сообщении #865760 писал(а):

Так

Значит, неверно, что

dmitgu в сообщении #865393 писал(а):

Какой результат работы будет у Анти-МТ можно узнать за полиномиальное время

?

[dmitgu]

warlock66613 в сообщении #865764 писал(а):

dmitgu в сообщении #865760 писал(а):

Так

Значит, неверно, что

dmitgu в сообщении #865393 писал(а):

Какой результат работы будет у Анти-МТ можно узнать за полиномиальное время

?

Это как раз верно - даже и без уточнений. Просто смотрим блок результата - он там.

[warlock66613]

Если можно узнать результат за полиномиальное время, то $AntiMT \in \mathbb P$, но тогда $AntiMT$ не может быть контрпримером.

[dmitgu]

warlock66613 в сообщении #865776 писал(а):

Если можно узнать результат за полиномиальное время, то $AntiMT \in \mathbb P$, но тогда $AntiMT$ не может быть контрпримером.

Нет, потому что "узнать за полиномиальное время, какой будет результат работы алгоритма" и "алгоритм даст результат за полиномиальное время" - это разные вещи. Анти-МТ работает очень долго. Как и алгоритм сложения миллиард раз числа миллиард. Но узанать, чему равен квадрат миллиарда - можно быстро.

[warlock66613]

dmitgu не путайте алгоритм и задачу. $\mathbb P$ и $\mathbb {NP}$ - это классы задач, а не алгоритмов.

[dmitgu]

warlock66613 в сообщении #865797 писал(а):

dmitgu не путайте алгоритм и задачу. $\mathbb P$ и $\mathbb {NP}$ - это классы задач, а не алгоритмов.

Гм... Вроде вопрос был про разницу между "узнать результат алгоритма" и "алгорит выдал результат". Я на него отвечал.

[warlock66613]

Понимаете, алгоритм как таковой не может быть контрпримером к $\mathbb P = \mathbb {NP}$, так как это классы задач, а не алгоритмов. Контрпримером может быть задача "определить результат работы алгоритма", но для этого алгоритм должен быть таким, чтобы нельзя было решить эту задачу за полиномиальное время. Для этого недостаточно, чтобы алгоритм был неполиномиальным, надо чтобы его нельзя было заменить никаким другим полиномиальным.

[Xaositect]

dmitgu в сообщении #865800 писал(а):

Гм... Вроде вопрос был про разницу между "узнать результат алгоритма" и "алгорит выдал результат". Я на него отвечал.

Если результат алгоритма можно узнать за полиномиальное время, то задача, которую этот алгоритм решает, принадлежит $\mathrm{P}$.

[dmitgu]

Xaositect в сообщении #865806 писал(а):

Если результат алгоритма можно узнать за полиномиальное время, то задача, которую этот алгоритм решает, принадлежит $\mathrm{P}$.

А как его узнать за полиномиальное время, если он работает долго? Нужно иметь доказательство (сертификат) как именно его узнать быстро. Ну, или функцию МТ (если вопрос про $NP = P$ решен положительно).

[warlock66613]

Стоп. Я понял. "Узнать результат работы" в терминологии dmitgu - это значит "посмотреть, что получилось".