Re: P = NP Что мне делать?
От: Sinix  
Дата: 07.10.09 07:15
Оценка: +2 :))) :)))
Здравствуйте, novako, Вы писали:

Ну дык приведите ваш пример np-полной задачи и как вы её решаете.
За одно нахождение сверхбольших простых/разложение на множители/дискретные логарифмы вам безопасники памятник поставят. Посмертно (с).
P = NP Что мне делать?
От: novako  
Дата: 06.10.09 19:49
Оценка: :))) :)))
Наверное мне удалось найти решение NP-трудных задач. Как утверждает теория это значит что можно решить любую из них. Или по крайней мере в конкретном приложении знаю как свести число перебора вариантов до n^4 или n^5 в отличии от полного перебора например n!. Надеюсь что не ошибся. Писал письма Джонсону, институт Клея, Аарону — не ответа не привета. Вопрос что мне с этим делать? Пока что реализовал для кроссвордов, решил сделать на их составлении бизнес больше ни чего не придумал. А вы уважаемые его к тому же это расскритиковали.мой пост
Автор: novako
Дата: 05.10.09


07.10.09 16:03: Перенесено модератором из 'Этюды для программистов' — Кодт
NP
Re: P = NP Что мне делать?
От: DSblizzard Россия  
Дата: 15.11.09 04:17
Оценка: 2 (1) -1 :)))
Здравствуйте, novako, Вы писали:

N>Писал письма Джонсону, институт Клея, Аарону — не ответа не привета.


Вы просто плохо знакомы с соответствующей литературой. Эта задача уже давно решена. P = NP в том и только том случае, когда P = 0 или N = 1.
Программировать сложно. Но не программировать еще сложнее.
Re[2]: P = NP Что мне делать?
От: kochetkov.vladimir Россия https://kochetkov.github.io
Дата: 07.10.09 13:13
Оценка: +1 :))) :)
Здравствуйте, Sinix, Вы писали:

S>Здравствуйте, novako, Вы писали:


S>Ну дык приведите ваш пример np-полной задачи и как вы её решаете.

S>За одно нахождение сверхбольших простых/разложение на множители/дискретные логарифмы вам безопасники памятник поставят. Посмертно (с).

Да нет, почему же посмертно. Мы на него живого памятник поставим

[Интервью] .NET Security — это просто
Автор: kochetkov.vladimir
Дата: 07.11.17
Re[7]: P = NP Что мне делать?
От: kl Германия http://stardog.com
Дата: 07.10.09 19:15
Оценка: 42 (3)
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Трурль, Вы писали:


Т>>А может и наоборот. Полиномиальный алгоритм Хачияна хуже чем экспоненциальный симплекс-метод.


К>А если Хачияну и симплексу скормить стотыщмильёнов данных? Кто кого переборет?


Не надо никаких стомилионных данных. Для симплекса известны патологические случаи, на которых он сваливается в экспоненту. Он хорош именно тем, что в реальных моделях такие случаи встречаются крайне редко.
А алгоритм Хачияна, кстати говоря, относится к категории алгоритмов, которые создавали не для реализации. Он этим показал полиномиальность самой задачи LP и это было целью. Прошло немало времени до появления алгоритмов interior point, которые полиномиальны и реализуются. Правда используются все равно пореже симплекса (хотя мне приходилось на высокодегенеративных задачах переключать glpk на interior point).
no fate but what we make
Re[2]: P = NP Что мне делать?
От: ghost92  
Дата: 07.10.09 09:52
Оценка: :))
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, novako, Вы писали:


N>>Наверное мне удалось найти решение NP-трудных задач. Вопрос что мне с этим делать? Пока что реализовал для кроссвордов


А>Мне удалось построить вечный двигатель (КПД пока небольшое — 115%, что, впрочем, выше чем аналогичные электродвигатели). Думаю теперь как заработать на идее. Пока в планах — создание мини-предприятия по производству и продажи экономичных грелок. Что думает общественность по поводу перспективности этого направления?


115% это уже неплохо.
А на машину такой поставить можно? Т.е. если не тормозить ну например ехать по трассе. То можно ездить без дозаправки? А то надоело за этот бензин платить.
Патент уже есть?
Готов профинансировать проект.
Какие первоначальные вложения?
Re[3]: P = NP Что мне делать?
От: LaptevVV Россия  
Дата: 08.10.09 04:58
Оценка: 9 (1)
Здравствуйте, kochetkov.vladimir, Вы писали:

LVV>>Статью на arxiv.org — срочно. На английском.

KV>Давно хотел спросить, а что дает публикация статьи именно там?
Бесспорный международный приоритет.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re: P = NP Что мне делать?
От: 8086  
Дата: 07.10.09 07:05
Оценка:
Полагаю, что человек нашедший, что P == NP не спрашивает на форумах, что с этим делать Кстати, сложность NP не O(n!) a O(2^n).

N>Наверное мне удалось найти решение NP-трудных задач. Как утверждает теория это значит что можно решить любую из них. Или по крайней мере в конкретном приложении знаю как свести число перебора вариантов до n^4 или n^5 в отличии от полного перебора например n!. Надеюсь что не ошибся. Писал письма Джонсону, институт Клея, Аарону — не ответа не привета. Вопрос что мне с этим делать? Пока что реализовал для кроссвордов, решил сделать на их составлении бизнес больше ни чего не придумал. А вы уважаемые его к тому же это расскритиковали.мой пост
Автор: novako
Дата: 05.10.09
Re: P = NP Что мне делать?
От: nikov США http://www.linkedin.com/in/nikov
Дата: 07.10.09 07:22
Оценка:
Здравствуйте, novako, Вы писали:

N>Наверное мне удалось найти решение NP-трудных задач. Вопрос что мне с этим делать?


А не мог бы ты для начала дать определение классов P, NP и NP-complete?
Re: P = NP Что мне делать?
От: Аноним  
Дата: 07.10.09 09:25
Оценка:
Здравствуйте, novako, Вы писали:

N>Наверное мне удалось найти решение NP-трудных задач. Вопрос что мне с этим делать? Пока что реализовал для кроссвордов


Мне удалось построить вечный двигатель (КПД пока небольшое — 115%, что, впрочем, выше чем аналогичные электродвигатели). Думаю теперь как заработать на идее. Пока в планах — создание мини-предприятия по производству и продажи экономичных грелок. Что думает общественность по поводу перспективности этого направления?
Re: P = NP Что мне делать?
От: Буравчик Россия  
Дата: 07.10.09 09:58
Оценка:
Здравствуйте, novako, Вы писали:

N>Наверное мне удалось найти решение NP-трудных задач.


Есть такая задача Задача выполнимости булевых формул (SAT или ВЫП). Она является NP-полной.

Есть также соревнования по решению указанной задачи. См. http://www.satcompetition.org/. Там представлены задачи (большой размерности) и сами решатели (solver).

Если Вы сможете написать SAT-solver, который в несколько раз лучше, чем победитель, то я уверен, что сообщение об этом никто не оставит без внимания. Если решение NP трудных задач действительно найти удалось, то у Вас все получится. Это и будет необходимый минимум, подтверждающий правильность Ваших выводов.

Или у Вас есть доказательство P=NP? Тогда его надо выносить на суд общественности. Для поиска ошибок
Best regards, Буравчик
Re[2]: P = NP Что мне делать?
От: Кодт Россия  
Дата: 07.10.09 10:35
Оценка:
Здравствуйте, Буравчик, Вы писали:

Б>Если Вы сможете написать SAT-solver, который в несколько раз лучше, чем победитель, то я уверен, что сообщение об этом никто не оставит без внимания. Если решение NP трудных задач действительно найти удалось, то у Вас все получится. Это и будет необходимый минимум, подтверждающий правильность Ваших выводов.


Известно, что игра "сапёр" является частным случаем SAT. Это было показано путём двоичной схемотехники на минных полях.
Однако ясно, что в реальной жизни не встречаются ни такие здоровенные поля, ни такие подлые расположения мин, чтобы игроку пришлось тратить крендельон лет на решение задачи перебором.

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

А SAT-конкурсы проводятся на дистиллированных задачах, а не на таких вот "частных случаях".
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[3]: P = NP Что мне делать?
От: Буравчик Россия  
Дата: 07.10.09 10:43
Оценка:
Здравствуйте, Кодт, Вы писали:

К> ...


Я согласен со всем, что написано в сообщении, но не понял, что из этого следует
Best regards, Буравчик
Re[4]: P = NP Что мне делать?
От: Кодт Россия  
Дата: 07.10.09 11:08
Оценка:
Здравствуйте, Буравчик, Вы писали:

Б>Я согласен со всем, что написано в сообщении, но не понял, что из этого следует


Из этого следует, что у топикстартера может быть сколь угодно революционный эвристический генератор кроссвордов, но по-прежнему экспоненциальный.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[3]: P = NP Что мне делать?
От: novako  
Дата: 07.10.09 11:10
Оценка:
Здравствуйте, Кодт, Вы писали:

К>То же самое и с кроссвордами. На каких-то сетках и словарях коэффициент при экспоненте большой, а на подавляющем количестве реальных примеров — крошечный.

К>Плюс всякие эвристики, заточенные именно под человеческие словари.

и в результате имеет одинаковые кроссворды с теме же самыми сетками и теме же словами, но разными определениями(заданиями) к ним.
Re[2]: P = NP Что мне делать?
От: novako  
Дата: 07.10.09 11:11
Оценка:
Здравствуйте, Sinix, Вы писали:

S>Здравствуйте, novako, Вы писали:


S>Ну дык приведите ваш пример np-полной задачи и как вы её решаете.

S>За одно нахождение сверхбольших простых/разложение на множители/дискретные логарифмы вам безопасники памятник поставят. Посмертно (с).

Еще об этом не думал, да и желания думать нет, положительного смысла в этом мало.
Re[5]: P = NP Что мне делать?
От: novako  
Дата: 07.10.09 11:15
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Буравчик, Вы писали:


Б>>Я согласен со всем, что написано в сообщении, но не понял, что из этого следует


К>Из этого следует, что у топикстартера может быть сколь угодно революционный эвристический генератор кроссвордов, но по-прежнему экспоненциальный.


В ходе исследований которыми без малого я занимаюсь 10 лет, действительно от экспоненты не уйти, по крайней мера пока что не удалось, ее лишь можно существенно минимизировать. И для решения не общей а реальной задачи вполне приемлемо, а собственно что еще нужно? Если есть возможность решать задачи из жизни за которые деньги платят. В тоже время если например разработать алгоритм который будет эффективно решать задачу составления расписания — согласитесь что это куда перспективнее и нужнее чем кроссворды.
Re[4]: P = NP Что мне делать?
От: midcyber
Дата: 07.10.09 11:31
Оценка:
Здравствуйте, Буравчик, Вы писали:

Б>Я согласен со всем, что написано в сообщении, но не понял, что из этого следует :)


Я не понял ничего, что написано в том сообщении, но согласен со всем.
Re[2]: P = NP Что мне делать?
От: CreatorCray  
Дата: 07.10.09 12:08
Оценка:
Здравствуйте, Sinix, Вы писали:

S>За одно нахождение сверхбольших простых/разложение на множители/дискретные логарифмы вам безопасники памятник поставят. Посмертно (с)

Именно! Тока сперва еще и помучаем, чтоб другим неповадно было!
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re: P = NP Что мне делать?
От: LaptevVV Россия  
Дата: 07.10.09 12:47
Оценка:
Здравствуйте, novako, Вы писали:

N>Наверное мне удалось найти решение NP-трудных задач. Как утверждает теория это значит что можно решить любую из них. Или по крайней мере в конкретном приложении знаю как свести число перебора вариантов до n^4 или n^5 в отличии от полного перебора например n!. Надеюсь что не ошибся. Писал письма Джонсону, институт Клея, Аарону — не ответа не привета. Вопрос что мне с этим делать? Пока что реализовал для кроссвордов, решил сделать на их составлении бизнес больше ни чего не придумал. А вы уважаемые его к тому же это расскритиковали.мой пост
Автор: novako
Дата: 05.10.09

Статью на arxiv.org — срочно. На английском.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[5]: P = NP Что мне делать?
От: Трурль  
Дата: 07.10.09 13:04
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Из этого следует, что у топикстартера может быть сколь угодно революционный эвристический генератор кроссвордов, но по-прежнему экспоненциальный.


А может и наоборот. Полиномиальный алгоритм Хачияна хуже чем экспоненциальный симплекс-метод.
Re[2]: P = NP Что мне делать?
От: novako  
Дата: 07.10.09 13:38
Оценка:
Здравствуйте, LaptevVV, Вы писали:

LVV>Здравствуйте, novako, Вы писали:


N>>Наверное мне удалось найти решение NP-трудных задач. Как утверждает теория это значит что можно решить любую из них. Или по крайней мере в конкретном приложении знаю как свести число перебора вариантов до n^4 или n^5 в отличии от полного перебора например n!. Надеюсь что не ошибся. Писал письма Джонсону, институт Клея, Аарону — не ответа не привета. Вопрос что мне с этим делать? Пока что реализовал для кроссвордов, решил сделать на их составлении бизнес больше ни чего не придумал. А вы уважаемые его к тому же это расскритиковали.мой пост
Автор: novako
Дата: 05.10.09

LVV>Статью на arxiv.org — срочно. На английском.

Да но алгоритм то это секрет! А сравнительные результаты это пожалуйста!
Re[6]: P = NP Что мне делать?
От: Кодт Россия  
Дата: 07.10.09 13:44
Оценка:
Здравствуйте, Трурль, Вы писали:

Т>А может и наоборот. Полиномиальный алгоритм Хачияна хуже чем экспоненциальный симплекс-метод.


А если Хачияну и симплексу скормить стотыщмильёнов данных? Кто кого переборет?
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[3]: P = NP Что мне делать?
От: samius Россия http://sams-tricks.blogspot.com
Дата: 07.10.09 13:47
Оценка:
Здравствуйте, novako, Вы писали:

N>Да но алгоритм то это секрет! А сравнительные результаты это пожалуйста!


Я работал в одной госконторе, где можно было на совершенно секретной защите защитить marching cubes. Был такой прецедент года 3 назад. Чем хреновее диссер, тем больше секрет! Это я так, вспомнилось
Re[4]: P = NP Что мне делать?
От: novako  
Дата: 07.10.09 13:54
Оценка:
Здравствуйте, samius, Вы писали:

S>Здравствуйте, novako, Вы писали:


N>>Да но алгоритм то это секрет! А сравнительные результаты это пожалуйста!


S>Я работал в одной госконторе, где можно было на совершенно секретной защите защитить marching cubes. Был такой прецедент года 3 назад. Чем хреновее диссер, тем больше секрет! Это я так, вспомнилось


Да, но если я прав, моя прога действительно быстрая, очень быстрая. Я знаю о других результатах близко не валялись.
Re[5]: P = NP Что мне делать?
От: nikov США http://www.linkedin.com/in/nikov
Дата: 07.10.09 13:58
Оценка:
Здравствуйте, novako, Вы писали:

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


Ну сделай web-service для решения SAT. Сначала бесплатный, а как раскрутишься, бери деньги.
Потом запатентуй и опубликуй.
Re[2]: P = NP Что мне делать?
От: kochetkov.vladimir Россия https://kochetkov.github.io
Дата: 07.10.09 13:59
Оценка:
Здравствуйте, LaptevVV, Вы писали:

LVV>Статью на arxiv.org — срочно. На английском.


Давно хотел спросить, а что дает публикация статьи именно там?

[Интервью] .NET Security — это просто
Автор: kochetkov.vladimir
Дата: 07.11.17
Re[5]: P = NP Что мне делать?
От: samius Россия http://sams-tricks.blogspot.com
Дата: 07.10.09 14:00
Оценка:
Здравствуйте, novako, Вы писали:

N>Здравствуйте, samius, Вы писали:


S>>Здравствуйте, novako, Вы писали:


N>>>Да но алгоритм то это секрет! А сравнительные результаты это пожалуйста!


S>>Я работал в одной госконторе, где можно было на совершенно секретной защите защитить marching cubes. Был такой прецедент года 3 назад. Чем хреновее диссер, тем больше секрет! Это я так, вспомнилось


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


Что прога действительно быстрая — верю. Что P = NP — нет.

Я же не в укор про секретные защиты. Просто навеяло.
Кстати, там где я работал, про NP тоже мало кто слышал. Потому прокатило бы
Re[5]: P = NP Что мне делать?
От: Буравчик Россия  
Дата: 07.10.09 17:51
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Из этого следует, что у топикстартера может быть сколь угодно революционный эвристический генератор кроссвордов, но по-прежнему экспоненциальный.


Все правильно. Но, чем SAT хорош?

Пусть удалось сделать лучший SAT-solver. Даже если просто найдена какая-то серьезная эвристика (перенесли эвристику с кроссвордов на SAT), то это уже результат, интересный сам по себе. К тому же это покажет, что в устах топикстартера слова "P=NP" может что-то да значат.

Ну, а если не удалось — то ни эвристики, ни P=NP нет и близко, следовательно имеется где-то ошибка. Или имеется эвристика лишь для какого-то частного случая с кроссвордами.

Да и сам алгоритм показывать не надо. Сделал, замерил, сравнил с другими — опубликовал результаты / нашел ошибку.
... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>
Best regards, Буравчик
Re[6]: P = NP Что мне делать?
От: novako  
Дата: 08.10.09 04:21
Оценка:
Б>Пусть удалось сделать лучший SAT-solver. Даже если просто найдена какая-то серьезная эвристика (перенесли эвристику с кроссвордов на SAT), то это уже результат, интересный сам по себе. К тому же это покажет, что в устах топикстартера слова "P=NP" может что-то да значат.

Б>Ну, а если не удалось — то ни эвристики, ни P=NP нет и близко, следовательно имеется где-то ошибка. Или имеется эвристика лишь для какого-то частного случая с кроссвордами.


Б>Да и сам алгоритм показывать не надо. Сделал, замерил, сравнил с другими — опубликовал результаты / нашел ошибку.


Может быть когдна нибудь сделаю SAT. Ошибки в алгоритме нет. Но можно наверное улучшить. Даже есть идея как. Но пока не уверен поможет ли это или нет. Скоро узнаем.
Re[5]: P = NP Что мне делать?
От: blackhearted Украина  
Дата: 06.11.09 15:43
Оценка:
Здравствуйте, novako, Вы писали:

N>Здравствуйте, samius, Вы писали:


S>>Здравствуйте, novako, Вы писали:


N>>>Да но алгоритм то это секрет! А сравнительные результаты это пожалуйста!


S>>Я работал в одной госконторе, где можно было на совершенно секретной защите защитить marching cubes. Был такой прецедент года 3 назад. Чем хреновее диссер, тем больше секрет! Это я так, вспомнилось


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


Топикстартер мне напонинает великого Рыбинкина с IXBT
Re[2]: P = NP Что мне делать?
От: novako  
Дата: 15.11.09 16:08
Оценка:
Здравствуйте, DSblizzard, Вы писали:

DS>Здравствуйте, novako, Вы писали:


N>>Писал письма Джонсону, институт Клея, Аарону — не ответа не привета.


DS>Вы просто плохо знакомы с соответствующей литературой. Эта задача уже давно решена. P = NP в том и только том случае, когда P = 0 или N = 1.


для многих задач p=np при p и n отличных от 0.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.