January 17th, 2015

ёжик

NP_primitive ≠ P. Завершение доказательства (надеюсь)

Копирую сюда свой пост с dxdy.ru - http://dxdy.ru/post963495.html#p963495
Но последний раздел ("Незавершенные вычисления") я выложу туда чуть позже - пока их форум не пропускает - слишком большая запись.

Похоже, мне удалось избавиться от расширительного толкования «проверки корректности» из
предыдущей записи ( http://dxdy.ru/post960183.html#p960183 ) и - таким образом - дать доказательство для NP_primitive ≠ P в традиционных рамках.

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

Collapse )