dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Программа Гильберта, NP ≠ P, Рефлексия


Оглавление


0. Аннотация

1. Задачи из классов NP и P, NP+ и P+ – 4 страницы

             п. 1, пп. 2-3, пп. 4-5.

2. Программа Гильберта и теория алгоритмов – 3,5 страницы

             п. 1, п. 2.

3. Сложность вопроса о NPP – 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. NPP – 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 (ссылка на скачивание будет внизу страницы)


Аннотация

[Нажмите, чтобы прочитать предисторию]
Предистория

Моё письмо в редакцию «Труды Московского Математического Общества» с предложенным доказательством NPP я отправил утром 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 при этом. Ужасно сомнительное завершение доказательства – если уж правда есть где-то такая теория, то отчего же её не найти, не построить, не предъявить? Было бы построение конструктивным – можно было бы предметно рассмотреть построенную задачу и аккуратно проверить её на наличие ошибок.

Поскольку принципиальные идеи построения «возражающих алгоритмов» являются правильной и проверенной методикой при доказательствах неразрешимости и неполноты в логике , то я искал, как применить их в теории алгоритмов и очень потихоньку стал выстраивать конструктивное доказательство:

Гипотеза (NPP) утверждает, что найти правильный ответ в общем случае – неполиномиально (то есть – «несоизмеримо») труднее, чем проверить его. Я строил массовую задачу из класса NP в которой у каждого алгоритма есть не решаемая для него подзадача. Алгоритм-решение либо окажется неспособен выдать результат о своей неспособности – что будет ошибкой (информация у него есть), либо будет тянуть с поиском ответа несоизмеримо со временем проверки, либо выдаст ответ «не могу найти решение», а при этом у подзадачи будет вполне конкретное решение.

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

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

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

Рефлексия – именно то, что мы используем каждый день – ведь задачи стоят передо мной (или моим коллективом) и я отличаю себя и свои задачи от чужих задач и других людей. И такая колоссальная сторона реальности не была раньше формализована в математике. А тут я наткнулся на возможность (необходимость даже) и формализовал. Алгоритмы, которые для правильного решения некоторых задач должны «понимать себя» и отличать от других алгоритмов. Формализация того, что имеет важнейшую роль в нашей обычной жизни. Это очень принципиальное открытие – на мой взгляд.

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

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


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