dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

Мое док-во (?) NP≠P и теорема М.Блюма

Речь идет о моем доказательстве:
NP не равно P. Мое «причесанное» доказательство задачи тысячелетия с уточнением:
Процесс разбора моего док-ва (?) NP≠P продолжается.

Прежде чем двигаться дальше (куда-то писать "выше"), я читаю теорию алгоритмов - что да как там раньше придумали. Напомню, что вроде мне даже показалось, что могу доказать NP≠P более традиционным способом (через результаты для Десятой проблемы Гильберта): Док-во NP≠P через диофантову неразрешимость (часть 4 из 4) , но потом нашел у себя ошибку (в каментах по ссылке сказано в чем). Поэтому читал дальше и нашел идеи очень родственные тем, которые я сам использовал в доказательстве. Перепишу инфу и сюда (копия с форума dxdy.ru):

Я тут выпал из обсуждения, потому что читал теорию алгоритмов. Оказывается, есть такая теорема М. Блюма о псевдоускорителе (и об ускорителе - в развитие), в которой доказано существование такой функции, что для каждого вычисляющего ее алгоритма $A_i$ найдется алгоритм$A_j$, вычисляющий ее почти всюду (кроме конечного числа точек) и почти всюду быстрее чем даже не просто алгоритм $A_i$, но даже быстрее чем его скорость, увеличенная произвольной функцией! Никак не мог несколько дней понять доказательство (из-за иных умолчаний, чем привык - максимум по пустому множеству оказывается они считают ноль, параметрический (по номеру) результат от применения заданной номером функции обозначен той же буквой что и для применяемых функции и т.п.).

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

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

Сейчас еще почитаю теорию алгоритмов недель пару и перепишу (если отчетный период не заставит отложить) свое доказательство как положено - формальным языком. Без апелляции к логике 2го порядка не обойтись, похоже, но это будет просто формальное упоминание...
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.
  • 6 comments