May 27th, 2014

ёжик

NP≠P - давно доказали через диофантову неразрешимость?

Вроде нет - см. 3ий комментарий из обсуждения.

Пытаюсь сейчас разобраться с теорией алгоритмов (там много дополнительного к знакомому мне из логики сведений о неразрешимости, выполнимости, неполноте и т.п.). Наверно я запутался от чтения, но вот какой вопрос:

Диофантовы уравнения ведь неразрешимы? И это задача из класса NP - за полиномиальное время можно проверить решает ли данный набор значений для переменных данное уравнение. Но! Задача поиска решения для диофантовых уравнений ведь неразрешима! То есть - не относится к классу P.

Но разве это не доказывает: NP ≠ P
????

Притом доказательство Ю.В. Матиясевича (о неразрешимости диофантовых уравнений в общем случае) вполне в духе заголовка данной темы - он строит перечислимое, но не разрешимое множество, строит диофантово множество (диофантово уравнение с параметром, если угодно)  для него (а он доказал, что это всегда можно) и оказывается, что если есть алгоритм решения диофантовых уравнений, то можно решить данное уравнение для каждого значения параметра и построить разрешающий это множество алгоритм. Что противоречит построенному диофантову множеству. А раз не существует разрешающий построенное диофантово множество алгоритм, то не существует и алгоритма для решения диофантовых уравнений. И такого решения нет - в том числе - и среди задач класса P.
Если все так, то теорема NP ≠ P давно доказана? Или где я запутался и что не понял?

Выложил этот вопрос в комментарий на dxdy.ru в своей теме о NP≠P.

Интересные комментарии (приведу несколько своих ответов с цитатами собеседика перед ними):
Collapse )