dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Процесс разбора моего док-ва (?) NP≠P продолжается.

А никто и не обещал, что будет быстро ) Тем более никто не обещал что прокатит в итоге и я получу миллион долларов ))
В общем, опубликовал (благодаря подсказкам гостей у Анатолия Вассермана - о чем писал раньше) на http://dxdy.ru/ еще вечером 18 мая - в воскресенье - в теме:
NP≠P. Док-во от противного-контрпример алгоритмов из NP

Пока доказательство успешно уточняется по нюансам, но не рушится. Предстоит уже второе уточнения со времен первого текста. Этот нюанс отловился с помощью warlock66613. Я ему отвечал -

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


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

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

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

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

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

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


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

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