В общем, опубликовал (благодаря подсказкам гостей у Анатолия Вассермана - о чем писал раньше) на http://dxdy.ru/ еще вечером 18 мая - в воскресенье - в теме:
NP≠P. Док-во от противного-контрпример алгоритмов из NP
Пока доказательство успешно уточняется по нюансам, но не рушится. Предстоит уже второе уточнения со времен первого текста. Этот нюанс отловился с помощью warlock66613. Я ему отвечал -
Доведу Ваш первый вопрос до требования к доказательству:
"Наличие способа проверки сертификата есть способ ограничить задачи рамками NP, а если этого нет, то от МТ потребуется (возможно) работать с набором задач, выходящим за рамки NP."
Но ограничить набор задач тут легко (вроде бы...). Придется еще добавить нюанс (как это сделать, чтоб старый текст сохранился и новый появился?):
Надо после абзаца с началом:
Ну, частью «ключа» является еще доказательство этой быстрой формулы расчета....
Поставить абзац:
Важный момент! Все-таки множеством интересующих нас алгоритмов будем считать те алгоритмы, для которых есть доказательство полиномиальной длины способа их быстрого расчета. Проверка доказательства имеет полиномиальную скорость (близкую к линейной), поэтому полиномиальность времени проверки при полиномиальном (от размера самого доказываемого утверждения) размере доказательства сохраняется. Тут нюанс в том, что при разных наборах аксиом будут разные выборки и если не задать отбор по доказательствам, то выборка может выйти в некоторых местах за пределы NP. Поэтому мы задаем и набор аксиом. Но он должен быть достаточно выразительным, чтоб алгоритмы могли анализировать свои тексты.
Следующий абзац в новой редакции:
Если у нас есть способ свести NP к P, то у нас должна быть и рассматриваемая нами МТ - потому что это тоже вариант «угадывания» быстрого решения, которое в принципе существует. Поэтому, наличие МТ - это необходимое условие того, чтобы NP = P. И если МТ не существует, то и NP не может равняться P.
После абзаца с началом:
Но у всего семейства Анти-МТ одинаковая структура и достаточно «глянуть» на конкретный экземпляр Анти-МТ, чтобы увидеть, что он из того самого семейства...
Поставить абзац:
К тому же про семейство Анти-МТ вполне можно доказать, как быстро посчитать результат у любого ее представителя. Ведь на месте МТ в Анти-МТ может стоять вообще любой алгоритм и он будет обманут или проигнорирован (когда время работы выйдет за контрольное). А после доказательства про «любой» он заменяется на МТ.
Следующий абзац в новой редакции:
Как видим, наш МТ заведомо не может «расколоть» Анти-МТ (какие-то из них) за полиномиальное время потому, что сам Анти-МТ построен как опровержение метода МТ (каким бы этот метод ни был). В то же время у нас есть почти линейный по времени работы метод для расчета результата работы Анти-МТ при корректном МТ и этот метод имеет полиномиальной длины доказательство. И «ключом» («сертификатом») для этого знания является сама структура построения Анти-МТ. То есть - быстрый способ вычисления Анти-МТ есть, но МТ его найти не может - вообще говоря.
Замечание:
После приведенных уточнений становится понятна причина невозможности МТ:
Наличие полиномиального доказательства для произвольного алгоритма, который можно быстро посчитать и который имеет такое док-во... Но! МТ подменяет собой тогда любое такое доказательство, а они могут быть сколь угодно большими. Вот тут, похоже, и находится противоречие, делающее невозможным существование. Ведь во все больших утверждения содержатся (в некоторых из них) все новые смыслы, которые изначально ограниченный МТ уже не в силах в себе содержать.
