dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

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

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

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

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

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

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

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

Интересные комментарии (приведу несколько своих ответов с цитатами собеседика перед ними):
Xaositect в сообщении #868253 писал(а):
В определении $\mathrm{NP}$ длина сертификата должна быть ограничена полиномом от длины аргумента. Длина записи корня уравнения не удовлетворяет этому условию.

Спасибо за это напоминание (я про него действительно забыл)! Но ведь это дело вроде легко поправимо (?) возможностью записывать диофантово уравнение с "мусором" типа непривиденного вида, вроде:
$5\time x_1^3 + 6\time x_1^3 + 3\time x_2^3 + 11\time x_2^3 + 126 + 941 = 0$

И при достаточном количестве "мусора" оно будет решено (приведено и посчитано). А слишком большие сертификаты да, будут отброшены и предикат будет выдавать ложь. Но по сути для всех уравнений будет свой вариант представления ("мусорного") при котором корни будут проверяемы (если они вообще есть), а вот разрешающего (в класс P) алгоритма заведомо не будет?

Я извиняюсь, если ерунду пишу - надо чтоб инфа в голове утряслась да и выспаться :) Но вот такой у меня довод пришел в голову. Если почувствую, что "не тяну" сейчас - отложим. И Вы тоже по самочувствию, естественно.

Xaositect в сообщении #868260 писал(а):
Надо, чтобы для любого уравнения, имеющего решение, был полиномиальный сертификат, а не только для специально построенных "замусоренных".
Так оно и есть - просто "чрезмерные" корни не относятся к полиномиальным. И в этом смысле - их нет. Мы берем усеченную до класса NP задачу на базе диофантовых уравнений. Но по сути без потери корней (всегда есть "мусорное" представление уравнения) и без потери факта неразрешимости - включая и несводимость к задаче из P.
Xaositect в сообщении #868275 писал(а):
Вот смотрите. Задача останова неразрешима. Но если мы возьмем не все программы, а только те, в которых нет циклов, то задача становится разрешимой. Здесь Вы тоже рассматриваете частный случай - не все уравнения, а только некоторые. Почему задача остается неразрешимой?
Гм... Хороший вопрос. Ясно, что в поиске решения каждой индивидуальной задачи из нашей массовой задачи из NP мы ищем среди ограниченного количества решений (с числом цифр не больше $L^3$ от длины уравнения). И в этом смысле алгоритм есть (хотя бы не полиномиальный). И тут еще вопрос - если есть разрешимость нашей задачи, то можно ли свести ее к разрешимости задачи о диофантовых уравнениях вообще. Если можно - тогда наша задача тоже неразрешима.
Тут надо подумать - может в этом и заковыка ) Я напишу в течение суток удалось или нет.
Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments