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

[arseniiv]

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

И благодаря я нашел несколько ошибок, например не было проверка на то что входное значение не должно быть 0, солвер просто сума сошел бедняга. Другой прислал пример в котором каждая строка содержала 1 цифру, тривиально, но надо было это предусмотреть.

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

[novako]

arseniiv в сообщении #851747 писал(а):

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

И благодаря я нашел несколько ошибок, например не было проверка на то что входное значение не должно быть 0, солвер просто сума сошел бедняга. Другой прислал пример в котором каждая строка содержала 1 цифру, тривиально, но надо было это предусмотреть.

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

Все программы и технологии нуждаются в тестировании. Так что это публичный бэта тест. Пока все идет хорошо.

[kp9r4d]

novako
Попробуйте создать тему на codeforces.ru с предложением взломать ваше решение, там таким заниматься любят.

[novako]

kp9r4d в сообщении #851756 писал(а):

novako
Попробуйте создать тему на codeforces.ru с предложением взломать ваше решение, там таким заниматься любят.

Объясните пожалуйста, что значит взломать? Если Вы имеете ввиду сайт, то боюсь что это бесполезно, т.е. сайт конечно поломают, но до решения не доберуться, это физически не возможно.

[kp9r4d]

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

Объясните пожалуйста, что значит взломать? Если Вы имеете ввиду сайт, то боюсь что это бесполезно, т.е. сайт конечно поломают, но до решения не доберуться, это физически не возможно.

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

[novako]

kp9r4d в сообщении #851772 писал(а):

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

Объясните пожалуйста, что значит взломать? Если Вы имеете ввиду сайт, то боюсь что это бесполезно, т.е. сайт конечно поломают, но до решения не доберуться, это физически не возможно.

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

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

-- Сб апр 19, 2014 17:20:21 --

kp9r4d в сообщении #851772 писал(а):

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

Объясните пожалуйста, что значит взломать? Если Вы имеете ввиду сайт, то боюсь что это бесполезно, т.е. сайт конечно поломают, но до решения не доберуться, это физически не возможно.

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

Мне прислали пример на 2700 строк, полным перебором поиск потребует 6,03e+812. У меня решение будет найдено в прогнозируемое время. Сколько пока точно не считал.

[kp9r4d]

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

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

Вам виднее сколько это. Задача ведь выявить «экспоненциальность» алгоритма, причём вслепую, поэтому тут такое дело: то, что выглядит как экспоненциальное время работы может оказаться плохой реализацией (т.е. полиномиальным временем но с плохими константами), и наоборот: то, что выглядит полиномиальным временем может оказаться очень хорошей эвристикой, в среднем работающей хорошо, например, на случайном тесте. Поэтому грубо говоря, такие «бета-тесты» они ни о чём. И у вас и у ваших идейных противников есть весомые аргументы в свою пользу, при любом времени работы на любом тесте, но хотя бы совсем грубую оценку дать можно (если пример из 40-50 множеств будет работать больше 2х часов, например, то это явно будет свидельство не в вашу пользу).
Профиль — начать собственный блог — написать в блог. Только для школьников там лишь CoderStrike, к тому же там многие школьники поумнее некоторых нешкольников будут, так что того: обижать СП сообщество не стоит :3

[novako]

kp9r4d в сообщении #851797 писал(а):

если пример из 40-50 множеств будет работать больше 2х часов, например, то это явно будет свидельство не в вашу пользу

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

[bin]

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

Слишком долго это сколько например?

И я хочу задать этот вопрос в отношении общего времени признания непредъявленного на общий суд алгоритма. Сравним с известной задачей 4х красок: там решение доступно в деталях, но т.к. никто не может его понять, то до сих пор:

Цитата:

Более тридцати лет группа математиков и программистов, руководимая Оре и Стемплом, строят на ЭВМ и раскрашивают плоские графы, надеясь найти контрпример... (В.В.Родионов, Методы четырехцветной раскраски вершин плоских графов, М.: КомКнига, 2005, С.12)

novako
Вы хотите ждать 30 лет? Те немногие, кого Вы уговорите искать контрпример, возможно, будут искать инфинитно долго, а остальные махнут рукой на Ваше заявление, полагая, что если не представлено доказательство, то не о чем и говорить. Таковы традиции не только математики, но и CS. В ближайшие десятилетия эти традиции вряд ли изменятся. Так что подумайте об упущенной за следующие 30 лет выгоде. Не лучше ли сразу сейчас получить лимон баксов за решение проблемы тысячелетия?

[novako]

Цитата:

Более тридцати лет группа математиков и программистов, руководимая Оре и Стемплом, строят на ЭВМ и раскрашивают плоские графы, надеясь найти контрпример... (В.В.Родионов, Методы четырехцветной раскраски вершин плоских графов, М.: КомКнига, 2005, С.12)

Ну это их дело. Я же хочу предложить сервис который будет решать задачи Exact Cover и SAT(тем же методом). Проверка правильности решения тривиальна. Как показывает практика задачи решаются все, впрочем как и теория. Далее заказчик дает задачу, мой сервис ее решает, дает ответ, если правильно, то со счета заказчика снимаются деньги, думаю понятно что мошенничество с моей стороны здесь исключено, потому что обмануть получиться ровно 1 раз))) Так как задача решается очень быстро, то заказчик не теряет даже время, на тот случай если вдруг ответ не удалось найти когда он есть.

[fiztech]

novako
Вы же решили эту задачу 5 лет назад. Почему именно сейчас активизировались ?

[g______d]

bin в сообщении #851958 писал(а):

Цитата:
Более тридцати лет группа математиков и программистов, руководимая Оре и Стемплом, строят на ЭВМ и раскрашивают плоские графы, надеясь найти контрпример... (В.В.Родионов, Методы четырехцветной раскраски вершин плоских графов, М.: КомКнига, 2005, С.12)

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

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

http://research.microsoft.com/en-us/um/ ... lproof.pdf

(ссылка на microsoft research, но примерно такой же текст опубликован в Notices of the AMS, http://www.ams.org/notices/200811/tx081101382p.pdf, но не уверен, что он у всех открывается).

Очень мало математических теорем доведено до такого уровня строгости.

[novako]

fiztech в сообщении #852016 писал(а):

novako
Вы же решили эту задачу 5 лет назад. Почему именно сейчас активизировались ?

Не решал и решил. Потому что появилось время. Распалась контора ИТ-шная в которой я работал, потому что заказчик был российским и на них повлияли санкции.

[bin]

g______d в сообщении #852043 писал(а):

Насколько я понимаю, доказательство проблемы четырех красок на данный момент формализовано и проверено компьютером в системе Coq.

В этом и проблема:

Цитата:

из-за точки зрения Гротендика на то, что доказательство должно заключаться в разбиении на ряд очевидных шагов он, например, не признал доказательство знаменитой «проблемы четырёх красок», которая была доказана при помощи вычислений на компьютере, причём его смущала не возможность ошибки программы или сбоя компьютера, сколько именно невозможность обозреть это доказательство для человека. (Википедия; Гротендик, Александр)

И такая точка зрения имеет право на существование

[g______d]

bin в сообщении #852083 писал(а):

И такая точка зрения имеет право на существование

Тем не менее, я не думаю, что Гротендик станет спорить с тем, что утверждение верно. И уверен, что никакие Оре и Стемпл никакие контрпримеры не ищут уже давно, и в 2005 году не искали.

Проблема всего лишь в отсутствии концептуального доказательства, которое можно было бы понять без большого перебора; текущее доказательство приносит в математику не так много, как хотелось бы.

Но бывает значительно хуже, например, классификация конечных простых групп.