NP не равно P. Мое «причесанное» доказательство задачи тысячелетия
Даю «причесанное» доказательство по результатам обсуждения в ЖЖ Онотоле. Первоначальное доказательство: NP != P. Я решил «задачу тысячелетия»? :). Первоначальное - заметно короче, но в нем пропущены некоторые очевидные для меня моменты. Тут, кстати видно, что когда чел «в теме», то он видит проблемы и решения в гораздо более «сжатом» виде и поэтому
( Read more... )
Comments 10
Есть класс NP-полных задач. Утверждение P=NP, используя определение NP-полноты, можно переформулировать следующим образом:
"Для каждой NP-полной задачи существует алгоритм, который решает эту задачу за полиномиальное время"
Утверждение же, которое опровергается в данном доказательстве звучит так:
"Существует единый алгоритм, который решает любую NP-полную задачу за полиномиальное время"
Для того чтобы доказательство было верным, необходимо показать эквивалентность этих утверждений, чего сделано не было.
Reply
Это продолжение дискуссии
Чтобы опровергнуть что "существует алгоритм, который решает NP-полную задачу за полиномиальное время" достаточно показать те задачи, которые алгоритм не решает. И эти нерешаемые задачи должны принадлежать клаcсу NP. Но ведь алгоритмы Анти-МТ принадлежат, вроде, классу NP?
Reply
Еще раз. Претензия не в этом.
Претензия в том, что опровергнуто утверждение неэквивалентное предположению P=NP.
Reply
1. Для каждой NP-полной задачи существует алгоритм, который решает эту задачу за полиномиальное время
2. Существует единый алгоритм, который решает любую NP-полную задачу за полиномиальное время
Гм... Но если задача NP-полная, то решение одной из них разве не решает и все прочие?
Reply
Leave a comment