2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 26  След.
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение20.05.2014, 23:07 
Аватара пользователя


18/05/14
215
Москва
warlock66613 в сообщении #865814 писал(а):
Стоп. Я понял. "Узнать результат работы" в терминологии dmitgu - это значит "посмотреть, что получилось". :-)

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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение20.05.2014, 23:12 
Заслуженный участник


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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение20.05.2014, 23:19 
Аватара пользователя


18/05/14
215
Москва
warlock66613 в сообщении #865822 писал(а):
"Узнать результат алгоритма за полиномиальное время" обычно означает "существует полиномиальный алгоритм, вычисляющий соответствующую общерекурсивную функцию". А что вы под этим подразумеваете внятно объяснить трудно. Но я понял.

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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение20.05.2014, 23:23 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение20.05.2014, 23:36 
Аватара пользователя


18/05/14
215
Москва
warlock66613 в сообщении #865827 писал(а):
Пусть даже ваше доказательство верно, и вы действительно приходите к противоречию. Но! Вы доказали, что не существует такого алгоритма, но вы не доказали, что $\mathbb P \ne \mathbb {NP}$.

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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение20.05.2014, 23:45 
Заслуженный участник


02/08/11
6874
dmitgu в сообщении #864939 писал(а):
есть МТ с заданным свойством. А интересует нас только то свойство, что для алгоритмов из NP она дает его результат из P (быстро).
Вы можете сформулировать это нормально? Кто даёт, какой результат? Что значит "результат из $\mathbb P$"?

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение20.05.2014, 23:57 
Аватара пользователя


18/05/14
215
Москва
warlock66613 в сообщении #865834 писал(а):
dmitgu в сообщении #864939 писал(а):
есть МТ с заданным свойством. А интересует нас только то свойство, что для алгоритмов из NP она дает его результат из P (быстро).
Вы можете сформулировать это нормально? Кто даёт, какой результат? Что значит "результат из $\mathbb P$"?


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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение21.05.2014, 00:18 
Заслуженный участник


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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение21.05.2014, 00:26 
Аватара пользователя


18/05/14
215
Москва
warlock66613 в сообщении #865849 писал(а):
а у вас один полиномиальный алгоритм на все задачи, которых, если я не ошибаюсь, счётное количество.

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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение21.05.2014, 00:34 
Заслуженный участник


02/08/11
6874
Ну как же не один?
dmitgu в сообщении #864939 писал(а):
МТ находит быстрые вычисления любого алгоритма Q
"Находит" - единственное число. "Любого" - много таких.

-- 21.05.2014, 01:38 --

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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение21.05.2014, 00:42 
Аватара пользователя


18/05/14
215
Москва
warlock66613 в сообщении #865861 писал(а):
Ну как же не один?
dmitgu в сообщении #864939 писал(а):
МТ находит быстрые вычисления любого алгоритма Q
"Находит" - единственное число. "Любого" - много таких.

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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение21.05.2014, 08:17 
Супермодератор
Аватара пользователя


20/11/12
5728
 ! 
dmitgu в сообщении #865760 писал(а):
NP = P
dmitgu, замечание за неоформление формул $\TeX$ом. Все формулы и термы нужно оформлять $\TeX$ом. В случае неоформления тема будет перенесена в Карантин.

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение21.05.2014, 21:00 
Аватара пользователя


18/05/14
215
Москва
Deggial в сообщении #865908 писал(а):
 ! 
dmitgu в сообщении #865760 писал(а):
NP = P
dmitgu, замечание за неоформление формул $\TeX$ом. Все формулы и термы нужно оформлять $\TeX$ом. В случае неоформления тема будет перенесена в Карантин.

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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение27.05.2014, 02:28 
Аватара пользователя


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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение27.05.2014, 02:34 
Заслуженный участник
Аватара пользователя


06/10/08
6422
dmitgu в сообщении #868252 писал(а):
Диофантовы уравнения ведь неразрешимы? И это задача из класса NP - за полиномиальное время можно проверить решает ли данный набор значений для переменных данное уравнение. Но! Задача поиска решения для диофантовых уравнений ведь неразрешима! То есть - не относится к классу P.
В определении $\mathrm{NP}$ длина сертификата должна быть ограничена полиномом от длины аргумента. Длина записи корня уравнения не удовлетворяет этому условию.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 384 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 26  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group