NP≠P. Док-во от противного-контрпример алгоритмов из NP

[dmitgu]

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]

dmitgu в сообщении #868258 писал(а):

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

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

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

[dmitgu]

Xaositect в сообщении #868260 писал(а):

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

Так оно и есть - просто "чрезмерные" корни не относятся к полиномиальным. И в этом смысле - их нет. Мы берем усеченную до класса NP задачу на базе диофантовых уравнений. Но по сути без потери корней (всегда есть "мусорное" представление уравнения) и без потери факта неразрешимости - включая и несводимость к задаче из P.

[Xaositect]

dmitgu в сообщении #868261 писал(а):

Так оно и есть - просто "чрезмерные" корни не относятся к полиномиальным. И в этом смысле - их нет. Мы берем усеченную до класса NP задачу на базе диофантовых уравнений. Но по сути без потери корней (всегда есть "мусорное" представление уравнения) и без потери факта неразрешимости - включая и несводимость к задаче из P.

Да, для любого полинома $Q$ задача "Имеет ли данное диофантово уравнение целое решение, длина которого ограничена числом $Q(n)$, где $n$ --- длина записи уравнения" принадлежит классу $\mathrm{NP}$.

[dmitgu]

Xaositect в сообщении #868262 писал(а):

Да, для любого полинома $Q$ задача "Имеет ли данное диофантово уравнение целое решение, длина которого ограничена числом $Q(n)$, где $n$ --- длина записи уравнения" принадлежит классу $\mathrm{NP}$.

Вот! Поэтому мне и кажется сейчас, что всё давно решено :) В смысле доказанности $NP \ne P$

[Xaositect]

Эта задача не является неразрешимой.

[dmitgu]

Xaositect в сообщении #868265 писал(а):

Эта задача не является неразрешимой.

Задача о решении диофантовых уравнений является неразрешимой - в Вики есть например (статья "Десятая проблема Гильберта").

Только там что-то почти не сказано про Матиясевича.

[Xaositect]

dmitgu в сообщении #868266 писал(а):

Задача о решении диофантовых уравнений является неразрешимой - в Вики есть например (статья "Десятая проблема Гильбарта").

Неограниченная задача ("Имеет ли данное диофантово уравнение целое решение?") является неразрешимой, но не принадлежит $\mathrm{NP}$. Ограниченная задача ("Имеет ли данное диофантово уравнение целое решение, длина которого ограничена числом $Q(n)$, где $n$ --- длина записи уравнения") принадлежит $\mathrm{NP}$, но не является неразрешимой.
Неограниченная задача не сводится к ограниченной, грубо говоря потому, что для того, чтобы определить, сколько именно мусора добавить в уравнение для того, чтобы решение стало полиномиальной длины, нужно узнать существование и длину решения, а это неразрешимая задача.

[dmitgu]

Xaositect в сообщении #868267 писал(а):

Неограниченная задача не сводится к ограниченной, грубо говоря потому, что для того, чтобы определить, сколько именно мусора добавить в уравнение для того, чтобы решение стало полиномиальной длины, нужно узнать существование и длину решения, а это неразрешимая задача.

Узнавать нет нужды, потому что среди бесконечного множества "мусорных" представлений найдутся и те, которые делают свои решения полиномиальными от длины данного "мусорного" представления.

[Xaositect]

dmitgu в сообщении #868268 писал(а):

Узнавать нет нужды, потому что среди бесконечного множества "мусорных" представлений найдутся и те, которые делают свои решения полиномиальными от длины данного "мусорного" представления.

И что это доказывает?

[dmitgu]

Xaositect в сообщении #868269 писал(а):

dmitgu в сообщении #868268 писал(а):

Узнавать нет нужды, потому что среди бесконечного множества "мусорных" представлений найдутся и те, которые делают свои решения полиномиальными от длины данного "мусорного" представления.

И что это доказывает?

Это доказывает то, что фактически любое диофантово уравнение будет иметь в классе NP соответствующий сертификат - если оно вообще имеет решение (хоть бы и неполиномиальное от приведенного вида уравнения). И в силу неразрешимости задачи об поиске решений диофантовых уравнений нет никакого алгоритма, рещающего эту задач с поиском сертификата (корней), вообще говоря. А раз нет никакого, то нет и полиномального по времени.

[Xaositect]

dmitgu в сообщении #868270 писал(а):

Это доказывает то, что фактически любое диофантово уравнение будет иметь в классе NP соответствующий сертификат - если оно вообще имеет решение (хоть бы и неполиномиальное от приведенного вида уравнения). И в силу неразрешимости задачи об поиске решений диофантовых уравнений нет никакого алгоритма, рещающего эту задач с поиском сертификата (корней), вообще говоря. А раз нет никакого, то нет и полиномального по времени.

Нет. Это доказывает, что разрешимое уравнение имеет сертификат, но мы не можем по уравнению даже вычислить длину сертификата, и потому не можем никак связать этот факт с классом $\mathrm{NP}$.

[dmitgu]

Xaositect в сообщении #868271 писал(а):

Нет. Это доказывает, что разрешимое уравнение имеет сертификат, но мы не можем по уравнению даже вычислить длину сертификата, и потому не можем никак связать этот факт с классом $\mathrm{NP}$.

Почему не можем? Вообще можно просто договориться, что длина корня не больше $L^3$, где L - длина диофантова уравнения (включая и мусорные представления). У нас же задача звучит не:

"Найти решение диофантового уравнения"
а
"Найти решение диофантова уравнения (включая "мусорное" представление) количество арабских цифр в котором не больше $L^3$, где L - длина данного уравнения"

И наша задача - из класса $\mathrm{NP}$ и столь же полная, как и исходная.

[Xaositect]

Что значит "включая мусорное представление"? На вход машине подается одна строка - уравнение, и длина сертификата должна быть полиномиально относительно именно этой строки, а не какого-то другого представления.

[dmitgu]

Xaositect в сообщении #868273 писал(а):

Что значит "включая мусорное представление"? На вход машине подается одна строка - уравнение, и длина сертификата должна быть полиномиально относительно именно этой строки, а не какого-то другого представления.

Ну да, так и будет. Просто для любого приведенного диофантова уравнения есть его не приведенные аналоги какой угодно длины. И если для приведенного уравнения есть только решения с длиной больше $L^3$, то для него в нашей постановке задачи решений нет вообще, но в нашей задаче это же уравнение представлено бесконечным множеством неприведенных уравнений и это же самое решение для бесконечного большинства таких представлений будет в рамках (в смысле количества цифр) $L^3$.