May 18th, 2014

ёжик

NP не равно P. Мое «причесанное» доказательство задачи тысячелетия

Даю «причесанное» доказательство по результатам обсуждения в ЖЖ Онотоле. Первоначальное доказательство: NP != P. Я решил «задачу тысячелетия»? :). Первоначальное - заметно короче, но в нем пропущены некоторые очевидные для меня моменты. Тут, кстати видно, что когда чел «в теме», то он видит проблемы и решения в гораздо более «сжатом» виде и поэтому значительно проще обнаруживает то, что ему надо. Поэтому прежнее доказательство остается полезным - чтоб кратко и наглядно уловить ключевые идеи. Теперь перейдем к более подробному варианту.

Смотрим Википедию - Задачи тысячелетия (цитата - до строки с многоточием):

Список проблем
Основная статья: Равенство классов P и NP

Если положительный ответ на какой-то вопрос можно быстро (за полиномиальное время) проверить (используя некоторую вспомогательную информацию, называемую сертификатом), то верно ли, что и сам ответ (вместе с сертификатом) на этот вопрос можно быстро найти? Задачи первого типа относятся к классу NP, второго — классу P. Проблема равенства этих классов является одной из важнейших проблем теории алгоритмов.
...

Ответ такой: Они не равны. То есть:
NP ≠ P

Доказательство  (Две с небольшим страницы А4).

Collapse )