June 19th, 2014

ёжик

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

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

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

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