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

[dmitgu]

warlock66613 в сообщении #865814 писал(а):

Стоп. Я понял. "Узнать результат работы" в терминологии dmitgu - это значит "посмотреть, что получилось".

"Посмотреть что получилось" - это как раз в Вашей терминологии. Это же Вы путает что такое "узнать результат алгоритма за полиномиальное время" и "алгоритм выдал результат за полиномиалное время". А я Вам объясняю разницу ;) А Вы не очень понимаете - но просто тема в области доказательств Вам наверно не очень привычна и накопилась усталость. Я без иронии. Давайте пусть у Вас немного уляжется вся эта новая инфа, потом легче обсудим. Я никуда не спешу. И, кстати, надо еще как-то доказательство дополнить - как я там выше написал.

[warlock66613]

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

[dmitgu]

warlock66613 в сообщении #865822 писал(а):

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

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

[warlock66613]

Я думаю можно идти дальше. Значит, вы вначале предполагаете, что существует алгоритм, который для каждой задачи из $\mathbb {NP}$ находит соответствующий полиномиальный алгоритм. Но ведь это гораздо более сильное предположение, чем $\mathbb P = \mathbb {NP}$. Пусть даже ваше доказательство верно, и вы действительно приходите к противоречию. Но! Вы доказали, что не существует такого алгоритма, но вы не доказали, что $\mathbb P \ne \mathbb {NP}$.

Кстати, я не уверен, насколько правильно называть контрпример к некоему утверждению, построенный в предположении истинности этого утверждения, контрпримером, но это не суть важно.

[dmitgu]

warlock66613 в сообщении #865827 писал(а):

Пусть даже ваше доказательство верно, и вы действительно приходите к противоречию. Но! Вы доказали, что не существует такого алгоритма, но вы не доказали, что $\mathbb P \ne \mathbb {NP}$.

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

[warlock66613]

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

есть МТ с заданным свойством. А интересует нас только то свойство, что для алгоритмов из NP она дает его результат из P (быстро).

Вы можете сформулировать это нормально? Кто даёт, какой результат? Что значит "результат из $\mathbb P$"?

[dmitgu]

warlock66613 в сообщении #865834 писал(а):

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

есть МТ с заданным свойством. А интересует нас только то свойство, что для алгоритмов из NP она дает его результат из P (быстро).

Вы можете сформулировать это нормально? Кто даёт, какой результат? Что значит "результат из $\mathbb P$"?

Ну, для произвольного алгоритма, для которого есть полиномиалное (от его размера) док-во как его быстро посчитать алгоритм МТ может дать быстрый результат его расчета. То есть, он решает проблему ссертификата (доказательства) и за полиномиальное время дает нужный результат (не имея изначально сертификата).

[warlock66613]

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

[dmitgu]

warlock66613 в сообщении #865849 писал(а):

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

Не, не один. Я же поэтому в доказательстве и вожусь, выделяя отдельный pp для Q. И обосновываю, что он должен быть. И даже в процессе доказательства показываю, что не важно, какой это pp.

[warlock66613]

Ну как же не один?

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

МТ находит быстрые вычисления любого алгоритма Q

"Находит" - единственное число. "Любого" - много таких.

-- 21.05.2014, 01:38 --

В общем я сдаюсь. Думаю, единственное, что вы можете сделать - это переписать ваше доказательство на формальном языке. Знаете, такой, с кванторами. Это нужно даже не как самоцель, просто вы в процессе осуществления этой задачи научитесь и на менее формальном, но всё же строгом, языке изъясняться, и вас смогут понять. Да вам и самому проще станет.

[dmitgu]

warlock66613 в сообщении #865861 писал(а):

Ну как же не один?

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

МТ находит быстрые вычисления любого алгоритма Q

"Находит" - единственное число. "Любого" - много таких.

А как написать? Вот дают алгоритм в МТ для расчета - если у алгоритма есть способ расчета за время квадрат от его длины и есть доказательство того же порядка, то МТ посчитает его быстро. Смысл вроде понятен.
Я предлагаю пойти спать ) Мне завтра бухучетом заниматься, потом ДР у сотрудника, пьянка может - предлагаю завтра продолжить (если не напьюсь :).

[Deggial]

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

NP = P

dmitgu, замечание за неоформление формул $\TeX$ом. Все формулы и термы нужно оформлять $\TeX$ом. В случае неоформления тема будет перенесена в Карантин.

[dmitgu]

Deggial в сообщении #865908 писал(а):

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

NP = P

dmitgu, замечание за неоформление формул $\TeX$ом. Все формулы и термы нужно оформлять $\TeX$ом. В случае неоформления тема будет перенесена в Карантин.

Я извиняюсь, что нарушил правила. Без привычки мне надо было быть внимательнее. Почитаю тут на сайте про редакторы $\TeX$ - чтоб не из Word копировать в окошко ответа, и посмотрю как формулы пишутся.

[dmitgu]

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

[Xaositect]

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

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

В определении $\mathrm{NP}$ длина сертификата должна быть ограничена полиномом от длины аргумента. Длина записи корня уравнения не удовлетворяет этому условию.