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

[novako]

Мне удалось построить алгоритм точного решения NP-полной задачи - точное покрытие (http://en.wikipedia.org/wiki/Exact_cover). Сделал сайт с решателем здесь http://npcomplete-001-site1.myasp.net/. Решение точное, метод точный, время полиномиальное, сложность $O(N^4)$ или меньше. На сайте доступен генератор тестов и его исходный код. Также есть результаты работы алгоритма, в ближайшие дни результатов будет больше. Также я разработал программу которая находит точное покрытие для заданных входных данных. Каждый из вас может воспользовавшись генератором создать текстовый файл с исходными данными, при чем в конце файла будет правильный ответ, который перед отправкой необходимо удалить. Конечно же Вы можете сделать такой тест в ручную, формат текстового файла примитивный. Если у меня нет алгоритма и программы то даже на самое не большое количество строк скажем 60, уйдет очень очень большое время 2^60 операций выбора и сравнения, даже если каждая операция будет занимать 1 такт процессора, даже при 100 мрлд операций в секунду, на нахождение решения потратится 11 млн сек.

[whitefox]

Вы забыли завершить сабж знаком вопроса:
"P=NP-Complete или задача тысячелетия решена?"

[novako]

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

Вы забыли завершить сабж знаком вопроса:
"P=NP-Complete или задача тысячелетия решена?"

Он-лайн солвер доступен. Люди уже тестируют.

[whitefox]

Это ни о чём не говорит.
Тесты построенные за несколько секунд (минут/часов) проходиться будут быстро. Действительно трудный тест можно построить только за существенно большее время.

Можете Вы представить тест, на который X-алгоритм Кнута потратит годы, а Ваш – минуты?

[novako]

У Кнута эвристический он не дает точного ответа гарантированно. Да такой тест есть, при чем не один. На счет годы не знаю, не пробовал дождаться, но время там было больше 2-х часов, дальше ждать не стал, у меня ответ нашло через 12 секунд. Могу выслать этот файл. И даже могу поискать сайт где я его взял. С другой стороны, может быть конечно солвер по Кнуту реализован не корректно, но мои тесты он не смог вообще выполнить.

[whitefox]

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

У Кнута эвристический он не дает точного ответа.

Вы имеете ввиду, что X-алгоритм Кнута недетерминированный?
Для его детерминированной реализации Кнут предложил "метод танцующий связей".
И находит он абсолютно все возможные точные покрытия. Что Вы понимаете под

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

не дает точного ответа

[novako]

Dansing Links - это реализация алгоритма Х. И остается эвристическим http://ru.wikipedia.org/wiki/%D0%AD%D0%B2%D1%80%D0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC

-- Сб апр 19, 2014 12:07:28 --

Был бы алгоритм Кнута точным, то не было бы и проблемы P vs NP. Потому что как минимум были бы решены NP-полные задачи, NP-трудные, это конечно сложение но для их решения всего лишь если в лоб надо было бы решать NP-полные до достижения минимума или максимума, сложность бы увеличилась всего лишь на порядок, т.е. имеем алгоритм для NP-Compelete O(N^k) для NP-Hard будет O(N^k+1).

[bin]

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

Решение точное, метод точный, время полиномиальное

Искренне поздравляю! Только где доказательство того, что "Решение точное, метод точный, время полиномиальное"? Так не делается, никто за Вас такие ребусы решать не будет. Напишите текст в виде статьи, как принято в таких случаях, с полным описанием Вашего решения и доказательством, что оно точное и полиномиальное. Такую статью можно выложить как на Ваш сайт, так и на arXiv.

[whitefox]

novako
Вы не ответили на мой вопрос:
"Какое решение задачи точного покрытия Вы называете точным?"

И почему, с Вашей точки зрения, алгоритм находящий абсолютно все возможные точные покрытия, "не даёт точного ответа"?

-- 19 апр 2014, 14:28 --

Согласен с bin. Без представленного доказательства, Ваши утверждения голословны.

[novako]

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

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

Решение точное, метод точный, время полиномиальное

Искренне поздравляю! Только где доказательство того, что "Решение точное, метод точный, время полиномиальное"? Может, я не разобрался в Вашем сайте, но кроме исполняемых файлов, там только исходный код Вашей программы. Причем какие-либо комментарии в этом коде отсутствуют. Т.о. предлагается некий "программистский ребус": убедитесь сами, что программа точная и полиномиальная. Так не делается, никто за Вас такие ребусы решать не будет. Напишите текст в виде статьи, как принято в таких случаях, с полным описанием Вашего решения и доказательством, что оно точное и полиномиальное. Алгоритм должен быть описан в словесной форме и/или на псевдокоде, причем это описание должно быть достаточным для независимой однозначной реализации Вашего алгоритма. Такую статью можно выложить как на Ваш сайт, так и на arXiv. Та программа, которую Вы выложили, - это только вспомогательный материал. Не хочу пугать, но Вы очень рискуете: сейчас идея Вашего решения доступна любому человеку через инет. Если кто-то все же сильно потрудится и сможет решить предложенный Вами ребус, то сможет Вас обокрасть, издав под своим именем статью, которую Вы не сделали, и Вам будет очень трудно доказать приоритет - все будут смотреть на статью, а не на исходный код программы. В лучшем случае будут говорить: доктор Х первым опубликовал строго доказанное решение задачи тысячелетия, несколько ранее novako на интуитивном уровне предложил похожее решение без доказательства.

Спасибо. На самом деле Вы не совсем разобрались. Выложен исходник программы для генерации тестов, которым Вы можете воспользоваться для того что бы проверить есть ли у меня решение или нет. Публиковать сам алгоритм и исходный код программы которая выполняет решение пока что считаю не возможным, по следующим причинам: 1) потом надо будет доказать что это сделал я 2)если решение правильное, то криптографии конец. В моих планах сделать сервис, который будет находить решения для многих NP-полных задач, и каждый кому потребуется сможет этим воспользоваться, за деньги разумеется, на самом деле реальные расчеты имеют весьма приличную себестоимость, не говоря уже об уникальности решения.

-- Сб апр 19, 2014 13:31:19 --

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

novako
Вы не ответили на мой вопрос:
"Какое решение задачи точного покрытия Вы называете точным?"

И почему, с Вашей точки зрения, алгоритм находящий абсолютно все возможные точные покрытия, "не даёт точного ответа"?

-- 19 апр 2014, 14:28 --

Согласен с bin. Без представленного доказательства, Ваши утверждения голословны.

Если бы алгоритм Кнута находил все решения, то тема была бы закрыта. Алгоритм эвристический, что это значит читайте в Википедии. Доказательством является мой сайт, на котором каждый может проверить что решение есть и оно точное.

[whitefox]

Алгоритм Кнута находит все решения, но его детерминированная реализация делает это за экспоненциальное время в худшем случае.
Так что тема не закрыта.

А доказательство в виде онлайн-солвера никого не убедит.
И мегабакс за такое "доказательство" не дадут.

-- 19 апр 2014, 14:54 --

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

Если бы алгоритм Кнута находил все решения

Если у Вас нет времени разбираться в чужих алгоритмах, то придётся положиться на мнение тех кто разобрался, вот одно из них:

http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X писал(а):

Donald Knuth's Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem

[bin]

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

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

Это ничего не доказывает. М.б. в Вашем распоряжении оказался быстрый компьютер или время на суперкомпе, м.б. Вы так же нашли эвристику, и контрпримеры для нее вслепую можно искать годами.

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

потом надо будет доказать что это сделал я

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

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

если решение правильное, то криптографии конец.

Ваше решение не означает конца криптографии. Даже алгоритмы с полиномами девятой степени по времени обычно оказываются слишком трудоемкими для практического использования.

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

сделать сервис, который будет находить решения для многих NP-полных задач, и каждый кому потребуется сможет этим воспользоваться, за деньги разумеется

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

[novako]

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

Алгоритм Кнута находит все решения, но его детерминированная реализация делает это за экспоненциальное время в худшем случае.
Так что тема не закрыта.

А доказательство в виде онлайн-солвера никого не убедит.
И мегабакс за такое "доказательство" не дадут.

-- 19 апр 2014, 14:54 --

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

Если бы алгоритм Кнута находил все решения

Если у Вас нет времени разбираться в чужих алгоритмах, то придётся положиться на мнение тех кто разобрался, вот одно из них:

http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X писал(а):

Donald Knuth's Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem

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

-- Сб апр 19, 2014 14:10:48 --

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

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

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

Это ничего не доказывает. М.б. в Вашем распоряжении оказался быстрый компьютер или время на суперкомпе, м.б. Вы так же нашли эвристику, и контрпримеры для нее вслепую можно искать годами.

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

потом надо будет доказать что это сделал я

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

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

если решение правильное, то криптографии конец.

Ваше решение не означает конца криптографии. Даже алгоритмы с полиномами девятой степени по времени обычно оказываются слишком трудоемкими для практического использования.

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

сделать сервис, который будет находить решения для многих NP-полных задач, и каждый кому потребуется сможет этим воспользоваться, за деньги разумеется

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

Супер компьютера у меня нет, какой у меня компьютер, написано на сайте на странице с результатами.
Пока что не хочу доказывать что я не олень.
У меня полином 4-й степени, и то как показывает практика в 100% случаев на много меньше.
Почему же частных и абстрактных, вопрос в интерфейсе приема данных. Во первых все NP-полные задачи сводятся к друг другу за полином, во-вторых если заказчик заинтересован в точном решении, то наверное приложит некоторые усилия что бы свои данные представить в нужном виде, тем более что это совсем не сложно.
По поводу взлома.. скажем так что криминального в том если мой сервис будет давать приватный PGP ключ в ответ на публичный?

[bin]

novako
Какая цель данной темы? Разобраться в предлагаемом решении важной проблемы или прорекламировать Ваш сервис "купите кота в мешке"? Если разобраться, то предоставьте текст, который можно обсуждать, если прорекламировать, то этот форум не для рекламы.

[novako]

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

novako
Какая цель данной темы? Разобраться в предлагаемом решении важной проблемы или прорекламировать Ваш сервис "купите кота в мешке"? Если разобраться, то предоставьте текст, который можно обсуждать, если прорекламировать, то этот форум не для рекламы.

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