2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3
 
 Re: P=NP-Complete или задача тысячелетия решена
Сообщение22.04.2014, 09:25 
Аватара пользователя
novako в сообщении #851969 писал(а):
Так как задача решается очень быстро, то заказчик не теряет даже время, на тот случай если вдруг ответ не удалось найти когда он есть.

А деньги он в этом случае теряет?
И если да, то как Вы его убедите, что это не мошенничество?
Что ответа на самом деле не существует? (Если заказчика интересует задача на решение которой X-алгоритму потребуются годы).

 
 
 
 Re: P=NP-Complete или задача тысячелетия решена
Сообщение22.04.2014, 09:58 
novako в сообщении #851903 писал(а):
Щас есть задачка на 2700 множеств, при чем очень хитро построенных, тут да долговато, но...

Современные промышленные sat-солверы играючи расправляются с проблемами, содержащими сотни тысяч переменных и миллионы дизъюнкций, так что тут пока хвастаться нечем.

-- Вт апр 22, 2014 10:53:10 --

whitefox в сообщении #852890 писал(а):
И если да, то как Вы его убедите, что это не мошенничество?
Что ответа на самом деле не существует?

Достаточно представить сертификат решения соответствующей $co\text{-}NP$ задачи. :wink:

 
 
 
 Re: P=NP-Complete или задача тысячелетия решена
Сообщение04.05.2014, 15:05 
Можно вопрос?
алгоритм похож на градиентный спуск в положение с наименьшей ошибкой?
если так, то он на промышленных запросах на размерность задачи уже не работает, проверено :-(
проверено на задаче изоморфизма графов, для 50 вершин персоналка уже загибается, хотя для 30 вершин -- работает, хотя $30!$ такое число, что работать не должна по видимому :-)
с глубоким уваженеием Билан И.

 
 
 
 Re: P=NP-Complete или задача тысячелетия решена
Сообщение05.05.2014, 00:33 
Аватара пользователя
Sender в сообщении #852903 писал(а):
Достаточно представить сертификат решения соответствующей $co\text{-}NP$ задачи.
И бедный заказчик потратит годы на его проверку. Так как полиномиальных сертификатов для $co\,\text{-}NP$ задач не существует.

 
 
 
 Re: P=NP-Complete или задача тысячелетия решена
Сообщение05.05.2014, 08:36 
Отчего же, вполне себе существует, коль скоро $P=NP$.

 
 
 
 Re: P=NP-Complete или задача тысячелетия решена
Сообщение05.05.2014, 08:41 
Аватара пользователя
Да, Вы совершенно правы.
Совсем упустил из виду, что ТС это доказал. :D

 
 
 
 Re: P=NP-Complete или задача тысячелетия решена
Сообщение25.05.2014, 20:12 
Ну что, ТС получил таки миллион долларов или нет? :D

 
 
 
 Re: P=NP-Complete или задача тысячелетия решена
Сообщение26.05.2014, 16:51 
Аватара пользователя
Интересно. Буду тестировать ваш метод. Послал первую задачу, но уже 10 минут нет ответа. Задачу взял с вашего сайта: http://npcomplete-001-site1.myasp.net/F ... ption.aspx

А сервер еще работает? У меня есть пара сложных задач которые хочу протестировать, но если сервер будет так долго работать то вряд ли есть смысл. Если долго нет ответа, как узнать что программа еще работает?

 
 
 
 Re: P=NP-Complete или задача тысячелетия решена
Сообщение27.05.2014, 04:05 
Аватара пользователя
Наконец получил емайл с ответом. Написано, что программа работала всего 0.1сек. Почему тогда так долго шло письмо?

Я узнал что вам уже посылали сложные задачи. Например, вам послали n-queens задачу и ваш метод долго работал. Он работал дольше чем обычные SAT солверы. Мой конструктивный совет: если вы хотите чтобы вашим методом заинтересовались то покажите код или по крайней мере опишите алгоритм. В таком деле скрытность приводит только к недоверию. Не волнуйтесь, даже если метод работает он НЕ поможет хакерам.

 
 
 [ Сообщений: 39 ]  На страницу Пред.  1, 2, 3


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group