dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Мое док-во NP ≠ P - пора готовить для публикации в математическом журнале?...

Копирую сюда свой пост с dxdy.ru (У них там время записи 11:19, но на самом деле 10:19 утра – на один час их часы опережают московское время):

http://dxdy.ru/post972938.html#p972938

Надо подвести промежуточные итоги и запланировать следующие действия.

Было сделано:

Предварительное эвристическое доказательство ( http://dxdy.ru/post954742.html#p954742 )

Сведения из учебников. Теорема о диагонализации в частности ( http://dxdy.ru/post956171.html#p956171 )

Моё первое формальное доказательство NPP тут с опорой на неразрешимость алгоритма проверки (для класса NP) + Определение AntiMt, вывод свойств ( http://dxdy.ru/post956292.html#p956292 )

Второе доказательство с расширенной проверкой корректности, но без опоры на неразрешимость проверки + Определение DiagKnockout(), вывод свойств ( http://dxdy.ru/post960183.html#p960183 )

Итоговое доказательство: Mt не может всегда прогнозировать AntiMt, хотя должен, когда есть аксиома DiagKnockout() ( http://dxdy.ru/post963495.html#p963495 )

Побочный разбор

По ходу построения доказательства возник «побочный» разбор нестыковок (на мой взгляд) в теории алгоритмов:

Класс - чрезмерное обобщение для NP, имхо. Скорее тип, вид - к которому ещё надо привести. Ну, например, не говорят о «классе» интегралов от дробно-рациональных функций - мы можем не знать, что данная функция равна дробно-рациональной, её надо ещё привести к нужному виду, а «класс» - это сразу готовый объект, независимо от вида. Но математик все же не бог, чтоб заранее знать всё.

Так же не могу согласиться - если подходить к этому строго - с обозначение NP P (или NP = P), потому что вопрос не о равенстве какой-то задачи из P некой задаче из NP, а о возможности за конечное время найти соответствующее решение из P для задачи из NP. Тут задача отчасти инженерная и такой практический параметр как время решения имеет принципиальное значение. В принципе, мое первое формальное доказательство тут обрывается именно после выявления невозможности свести при помощи конечного алгоритма некую задачу из класса NP к задаче из класса P. Можно, кстати, доказать неравенство классов и вне связи с алгоритмом сведения (выбранный метод работы с алгоритмом-опровержением AntiMt это позволяет), но это был бы ложный путь из-за необходимости - на мой взгляд - избавиться от использования тут понятия класса.

Есть и другие проблемы с определением задача из NP – в частности, возможность вырожденных (не значимых) частей у проверяемых слов, которые могут быть экспоненциально велики в сравнении со значимыми частями при нынешнем определении задач из NP.

Планы

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

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

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

Аннотация

Идея доказательства теоремы NP P типична для логики со времен теорем о неполноте и неразрешимости. А именно:

1. В качестве задачи NP строится задача на базе проверки доказательства для результата работы заданного алгоритма в заданной теории. В качестве проверяемого слова выступает пара – список аксиом теории и текст алгоритма. В качестве слова-свидетеля выступает текст доказательства.

2. Доказательство теоремы NP P ведется от противного: предполагается, что есть полиномиально быстрый алгоритм Mt(Aks, x) поиска нужного доказательства в теории с аксиомами Aks для алгоритма с текстом x. В целях опровержения данной гипотезы доказательства строится алгоритм AntiMt(Aks), который возвращает иной результат, чем предсказывает алгоритм Mt(Aks, «AntiMt(Aks)»).

3. Технически алгоритм AntiMt(Aks) строится при помощи стандартной для доказательств математической логики процедуры диагонализации. То есть, алгоритм AntiMt(Aks) «запускает» копию алгоритма Mt(Aks, x) с текстом своего – AntiMt – алгоритма, ждет результат работы и возвращает в качестве собственного результата иной результат, чем выдал алгоритм Mt(Aks, «AntiMt(Aks)»). Таким образом, алгоритм Mt(Aks, x) принципиально не может правильно предсказать результат работы алгоритма AntiMt(Aks).

Следующие 8 шагов – последовательные ограничения возможностей алгоритма Mt по выдаче правильного предсказания (или возможности отказа от предсказания) результата работы алгоритма AntiMt(). Эти ограничения завершаться невозможностью алгоритма Mt выдать правильный прогноз для AntiMt(), притом, что такой прогноз имеется среди доказательств соответствующей теории в пределах допустимых для доказательства размеров:

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

4. Для того, чтобы противоречивый результат работы Mt(Aks, x) входил в противоречие с проверкой слова-свидетеля (текстом доказательства) нашей задачи из NP мы сделаем предположение, что алгоритм проверки нашей задачи находит доказательство противоречия 1=0, если таковое имеется среди всех доказательств допустимой длины для данного проверяемого слова (аксиом теории и проверяемого алгоритма). Такая гипотеза полностью согласуется с п.3 о возможности полиномиально быстрого решения произвольной единичной задачи из NP.

5. Когда противоречие имеется, тогда любое доказательство, чей размер не меньше доказательства противоречия – считается ложным. Таким образом, выстраивается такая конструкция нашей задачи, при которой алгоритм решения Mt(Aks, «AntiMt(Aks)») не может вернуть никакой значимый результат, если его противоречивость будет вскрыта алгоритмом проверки. А любой значимый результат для Mt(Aks, «AntiMt(Aks)») является противоречивым – по построению (п. 3) алгоритма AntiMt(Aks).

6. Хотя любой значимый результат для Mt(Aks, «AntiMt(Aks)») является противоречивым, но не всякое противоречие будет вскрыто алгоритмом проверки из-за его возможной чрезмерной длины. Чтобы добиться достаточно короткого доказательства противоречия, мы будем рассматривать теории, содержащие в списке аксиом аксиому: Mt(Aks, «AntiMt(Aks)») = knockout

7. Это аксиома, которая утверждает, что алгоритм Mt(Aks, «AntiMt(Aks)») может вернуть лишь незначимый результат. И данное предложение – в некотором смысле является утверждением о себе самом, потому что это аксиома, которая зависит от списка аксиом Aks и при этом сама (точнее эквивалентное ему равенство) входит в список аксиом Aks. Данную аксиому назовём DiagKnockout(…) и так же, как и алгоритм AntiMt(…), построим при помощи процедуры диагонализации.

8. В случае, если аксиома DiagKnockout(…) расширяет непротиворечивую теорию, то алгоритм Mt(Aks + «DiagKnockout(Aks)», «AntiMt(...)») «вынужден» возвращать значимый результат. Потому что в данной теории имеется очень короткое доказательство для результата работы AntiMt(...) – в силу заданного аксиомой DiagKnockout(…) результата для Mt(Aks + «DiagKnockout(Aks)», «AntiMt(...)»), и в силу простой зависимости результата AntiMt(...) от результата работы Mt(Aks + «DiagKnockout(Aks)», «AntiMt(...)»).

9. При этом, если противоречивость значимого результата Mt(Aks + «DiagKnockout(Aks)», «AntiMt(...)») будет вскрыта проверкой, то работа алгоритма Mt(Aks + «DiagKnockout(Aks)», «AntiMt(...)») окажется некорректной. Но и отказаться от предсказания («согласиться» с DiagKnockout(…)) алгоритм Mt(Aks + «DiagKnockout(Aks)», «AntiMt(...)») тоже не может – иначе он не найдет короткого доказательства и не будет являться решением нашей задачи из NP, а аксиома DiagKnockout(…) окажется истинной и расширенная теория из п. 8 – непротиворечивой (что гарантирует корректность доказательства).

10. Таким образом, единственная возможность алгоритма Mt(Aks + DiagKnockout(…), «AntiMt(…)») остаться корректным решением – это случай выдачи значимого результата Mt(Aks + DiagKnockout(…), «AntiMt(…)») в каждом случае, когда есть расширение DiagKnockout(…) для непротиворечивой теории. Однако в таком случае истинным в стандартной интерпретации оказывается факт наличия противоречий всегда, когда есть аксиома DiagKnockout(…).

11. И добавление аксиомы об этом (доказуемости отрицания DiagKnockout(…), фактически) не сделает теорию противоречивой, но добавление DiagKnockout(…) к такой расширенной теории сделает невозможным корректный значимый результат работы для Mt(Aks + DiagKnockout(…), «AntiMt(…)»), что противоречит п. 9 и этим завершает доказательство.
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.
  • 7 comments