P=NP-Complete или задача тысячелетия решена

[whitefox]

novako в сообщении #851969 писал(а):

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

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

[Sender]

novako в сообщении #851903 писал(а):

Щас есть задачка на 2700 множеств, при чем очень хитро построенных, тут да долговато, но...

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

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

whitefox в сообщении #852890 писал(а):

И если да, то как Вы его убедите, что это не мошенничество?
Что ответа на самом деле не существует?

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

[bilan]

Можно вопрос?
алгоритм похож на градиентный спуск в положение с наименьшей ошибкой?
если так, то он на промышленных запросах на размерность задачи уже не работает, проверено
проверено на задаче изоморфизма графов, для 50 вершин персоналка уже загибается, хотя для 30 вершин -- работает, хотя $30!$ такое число, что работать не должна по видимому
с глубоким уваженеием Билан И.

[whitefox]

Sender в сообщении #852903 писал(а):

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

И бедный заказчик потратит годы на его проверку. Так как полиномиальных сертификатов для $co\,\text{-}NP$ задач не существует.

[Sender]

Отчего же, вполне себе существует, коль скоро $P=NP$.

[whitefox]

Да, Вы совершенно правы.
Совсем упустил из виду, что ТС это доказал.

[Rasool]

Ну что, ТС получил таки миллион долларов или нет?

[dimkadimon]

Интересно. Буду тестировать ваш метод. Послал первую задачу, но уже 10 минут нет ответа. Задачу взял с вашего сайта: http://npcomplete-001-site1.myasp.net/F ... ption.aspx

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

[dimkadimon]

Наконец получил емайл с ответом. Написано, что программа работала всего 0.1сек. Почему тогда так долго шло письмо?

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