Оглавление
1. Задачи из классов NP и P, NP+ и P+ – 4 страницы
2. Программа Гильберта и теория алгоритмов – 3,5 страницы
3. Сложность вопроса о NP ≠ P – 1,5 страницы
4. Предварительное замечание о программе Гильберта для теории алгоритмов – 1,5 страницы
5. Диагонализация.
5.1. Лемма о диагонализации – 3 страницы
5.2. Теорема о построении алгоритма, применяемого к себе – 2,5 страницы
6. Задачи Кука и авторизуемые задачи из класса NP – 8 страниц
п. 1, пп. 2.1-2.3, пп. 2.4-3, пп. 4-5.
7. NP ≠ P – 8,5 страниц
пп. 1-3, пп. 4-5, пп. 6.1-6.3, пп. 6.4-7.
8. Приложения
8.1. Первая теорема Гёделя о неполноте – 3 страницы
8.2. Вторая теорема Гёделя о неполноте – 2,5 страницы
8.3. Рефлексия. То, что все хотели знать о дилемме заключённого, но боялись спросить – 3,5 страницы
Скачать целиком в формате pdf с портала ЕДРИД: https://edrid.ru/rid/217.015.93d1.html (ссылка на скачивание будет внизу страницы)
Аннотация
[Нажмите, чтобы прочитать предисторию]Предистория
Моё письмо в редакцию «Труды Московского Математического Общества» с предложенным доказательством NP ≠ P я отправил утром 11 февраля 2015 г. Ответ с отказом в публикации пришёл вечером 27 апреля 2015 г. Довольно быстро, с учётом сложности их работы. И сопутствующая переписка (очень небольшая) была можно сказать дружелюбной и корректной по форме – что приятно, с учётом обращения к профи какого-то сумасшедшего любителя :).
Возражения рецензента были 2-х типов:
1. По «инструментам» (вроде: правильно представлять теоремы и алгоритмы через гёделевы номера, а не то представление, которое аналогично текстам программ или по методу из «Вычислимость и логика» Дж. Булоса, Р. Джеффри)
2. По пробелам в доказательстве (вроде вопроса о том, где я даю определение DiagKnockout(Aks))
По обоим типам возражений у меня были ответы, но поблагодарив и чуть упомянув о своих возражениях – не стал продолжать переписку. Мне не нравился неконструктивный характер предложенного мной тогда доказательства, и я понял, что используемый формализм надо обосновывать и пояснять, так как формализм Гёделя не подходит ко многим задачам теории алгоритмов: Вопросы логики о (не)существовании искомого ответа на бесконечности куда грубее, чем оценка времени и вопросы (не)существования ответов в полиномиальных рамках.
В процессе поиска конструктивного доказательства я нашёл ошибку в первоначальном неконструктивном доказательстве:
В своей первоначальной работе я строил задачу, в которой для произвольных алгоритмов ищется метод ускорить их вычисления. Например – сумма геометрической прогрессии может быть вычислена не только суммированием членов прогрессии, но и известной простой формулой. Чтоб «понять» (и найти) возможность ускорить вычисления, нужна какая-то теория и аксиомы Aks. И я построил алгоритм AntiMt(), который предполагаемый алгоритм-«ускоритель» Mt(…, …) не мог ни ускорить, ни вообще доказать его результат.
И я добавлял «диагональную» аксиому (несущую информацию о себе самой), сокращённо обозначу её DiagKnockout(Aks):
Mt(Aks, «AntiMt()») = knockout, означающую, что Mt(…, …) не может «придумать» результат работы AntiMt() в рамках теории с аксиомами Aks.
С другой стороны, вроде бы «полный» алгоритм-решение Mt(…, …) не должен возвращать признание в своей неспособности, после чего будет найден тот ответ, который не смог найти Mt(…, …). Отсюда, вроде бы, верно ~DiagKnockout(Aks). А там и противоречие можно получить и опровергнуть полноту Mt(…, …). Но ошибка в том, что я посчитал, что ~DiagKnockout(Aks) верный всегда при подстановке в непротиворечивую теорию про арифметику. Однако он не верен в случае наличия в данной теории аксиомы DiagKnockout(Aks), разумеется.
Это я сейчас упрощенно излагаю, а в той работе очевидные вещи были спрятаны диагонализациями и схемой аксиом. А противоречие между DiagKnockout(Aks) и ~DiagKnockout(Aks) опровергало – вроде бы – полноту. Но опровергало – неконструктивно. Типа «есть какая-то теория, в которой Mt(…, …) не найдёт ответ про AntiMt() и вернёт knockout при этом. Ужасно сомнительное завершение доказательства – если уж правда есть где-то такая теория, то отчего же её не найти, не построить, не предъявить? Было бы построение конструктивным – можно было бы предметно рассмотреть построенную задачу и аккуратно проверить её на наличие ошибок.
Поскольку принципиальные идеи построения «возражающих алгоритмов» являются правильной и проверенной методикой при доказательствах неразрешимости и неполноты в логике , то я искал, как применить их в теории алгоритмов и очень потихоньку стал выстраивать конструктивное доказательство:
Гипотеза (NP ≠ P) утверждает, что найти правильный ответ в общем случае – неполиномиально (то есть – «несоизмеримо») труднее, чем проверить его. Я строил массовую задачу из класса NP в которой у каждого алгоритма есть не решаемая для него подзадача. Алгоритм-решение либо окажется неспособен выдать результат о своей неспособности – что будет ошибкой (информация у него есть), либо будет тянуть с поиском ответа несоизмеримо со временем проверки, либо выдаст ответ «не могу найти решение», а при этом у подзадачи будет вполне конкретное решение.
В процессе построения нужной задачи оказалось, что прежний формализм для таких построений (гёделевы номера, стандартная модель интерпретации арифметики, машина Тьюринга) – слишком «грубые». Годятся для проверок существования ответов, которые неважно ценой какого размера построений и за какое время получены. А в теории алгоритмов размеры доказательств и время их поиска имеют принципиальное значение. Поэтому формализм метаматематики был уточнён (в некоторых учебниках он использовался и раньше – я упоминаю).
А затем выяснилось, что я строю не «классическую» задачу из класса NP, а нечто иное, но тоже – задачу из класса NP, хотя при этом теорема Кука к этой задаче не применима («авторизуемая задача»). И оказалось, что в «классических задачах» из класса NP не учитывается, что задача может содержать формализованную информацию о работе алгоритмов-решений и эта информация может быть разной для разных алгоритмов-решений.
И тут обнаружилась исключительно интересная возможность (необходимая для дальнейшей работы) - формализации рефлексии. Вот формализацию рефлексии я считаю самым интересным и принципиальным результатом своей работы, хотя удалось, вроде бы, доказать и неравенство NP ≠ P.
Рефлексия – именно то, что мы используем каждый день – ведь задачи стоят передо мной (или моим коллективом) и я отличаю себя и свои задачи от чужих задач и других людей. И такая колоссальная сторона реальности не была раньше формализована в математике. А тут я наткнулся на возможность (необходимость даже) и формализовал. Алгоритмы, которые для правильного решения некоторых задач должны «понимать себя» и отличать от других алгоритмов. Формализация того, что имеет важнейшую роль в нашей обычной жизни. Это очень принципиальное открытие – на мой взгляд.
Не уверен, что за время исследования в одиночку я не утратил в нём связь с реальностью, перестав замечать какие-то принципиальные ошибки. Но все построения в данной работе конструктивные, опираются на обычные методы работы с теориями первого порядка, строю даже пример действующей программы в подтверждение «Теоремы о построении алгоритма, применяемого к себе». И задача из NP, которую строю – вполне конкретная и может быть реализована хоть на уровне языка программирования (что было бы очень громоздкой работой, конечно). Всё это, надеюсь, поможет при чтении данной работы проще её понять и обнаружить не замеченные мной ошибки.
Как и в прошлый раз, хочу проверить построенные доказательства на математическом форуме (опубликовать в блоге, на форуме(ах) математиков, пообщаться ещё где-то), а уж если доказательства выдержат обсуждение – будет видно, что делать дальше.
