Наверное мне удалось найти решение NP-трудных задач. Как утверждает теория это значит что можно решить любую из них. Или по крайней мере в конкретном приложении знаю как свести число перебора вариантов до n^4 или n^5 в отличии от полного перебора например n!. Надеюсь что не ошибся. Писал письма Джонсону, институт Клея, Аарону — не ответа не привета. Вопрос что мне с этим делать? Пока что реализовал для кроссвордов, решил сделать на их составлении бизнес больше ни чего не придумал. А вы уважаемые его к тому же это расскритиковали.мой пост
Полагаю, что человек нашедший, что P == NP не спрашивает на форумах, что с этим делать Кстати, сложность NP не O(n!) a O(2^n).
N>Наверное мне удалось найти решение NP-трудных задач. Как утверждает теория это значит что можно решить любую из них. Или по крайней мере в конкретном приложении знаю как свести число перебора вариантов до n^4 или n^5 в отличии от полного перебора например n!. Надеюсь что не ошибся. Писал письма Джонсону, институт Клея, Аарону — не ответа не привета. Вопрос что мне с этим делать? Пока что реализовал для кроссвордов, решил сделать на их составлении бизнес больше ни чего не придумал. А вы уважаемые его к тому же это расскритиковали.мой пост
Ну дык приведите ваш пример np-полной задачи и как вы её решаете.
За одно нахождение сверхбольших простых/разложение на множители/дискретные логарифмы вам безопасники памятник поставят. Посмертно (с).
Здравствуйте, novako, Вы писали:
N>Наверное мне удалось найти решение NP-трудных задач. Вопрос что мне с этим делать?
А не мог бы ты для начала дать определение классов P, NP и NP-complete?
Re: P = NP Что мне делать?
От:
Аноним
Дата:
07.10.09 09:25
Оценка:
Здравствуйте, novako, Вы писали:
N>Наверное мне удалось найти решение NP-трудных задач. Вопрос что мне с этим делать? Пока что реализовал для кроссвордов
Мне удалось построить вечный двигатель (КПД пока небольшое — 115%, что, впрочем, выше чем аналогичные электродвигатели). Думаю теперь как заработать на идее. Пока в планах — создание мини-предприятия по производству и продажи экономичных грелок. Что думает общественность по поводу перспективности этого направления?
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, novako, Вы писали:
N>>Наверное мне удалось найти решение NP-трудных задач. Вопрос что мне с этим делать? Пока что реализовал для кроссвордов
А>Мне удалось построить вечный двигатель (КПД пока небольшое — 115%, что, впрочем, выше чем аналогичные электродвигатели). Думаю теперь как заработать на идее. Пока в планах — создание мини-предприятия по производству и продажи экономичных грелок. Что думает общественность по поводу перспективности этого направления?
115% это уже неплохо.
А на машину такой поставить можно? Т.е. если не тормозить ну например ехать по трассе. То можно ездить без дозаправки? А то надоело за этот бензин платить.
Патент уже есть?
Готов профинансировать проект.
Какие первоначальные вложения?
Есть также соревнования по решению указанной задачи. См. http://www.satcompetition.org/. Там представлены задачи (большой размерности) и сами решатели (solver).
Если Вы сможете написать SAT-solver, который в несколько раз лучше, чем победитель, то я уверен, что сообщение об этом никто не оставит без внимания. Если решение NP трудных задач действительно найти удалось, то у Вас все получится. Это и будет необходимый минимум, подтверждающий правильность Ваших выводов.
Или у Вас есть доказательство P=NP? Тогда его надо выносить на суд общественности. Для поиска ошибок
Здравствуйте, Буравчик, Вы писали:
Б>Если Вы сможете написать SAT-solver, который в несколько раз лучше, чем победитель, то я уверен, что сообщение об этом никто не оставит без внимания. Если решение NP трудных задач действительно найти удалось, то у Вас все получится. Это и будет необходимый минимум, подтверждающий правильность Ваших выводов.
Известно, что игра "сапёр" является частным случаем SAT. Это было показано путём двоичной схемотехники на минных полях.
Однако ясно, что в реальной жизни не встречаются ни такие здоровенные поля, ни такие подлые расположения мин, чтобы игроку пришлось тратить крендельон лет на решение задачи перебором.
То же самое и с кроссвордами. На каких-то сетках и словарях коэффициент при экспоненте большой, а на подавляющем количестве реальных примеров — крошечный.
Плюс всякие эвристики, заточенные именно под человеческие словари.
А SAT-конкурсы проводятся на дистиллированных задачах, а не на таких вот "частных случаях".
Здравствуйте, Кодт, Вы писали:
К>То же самое и с кроссвордами. На каких-то сетках и словарях коэффициент при экспоненте большой, а на подавляющем количестве реальных примеров — крошечный. К>Плюс всякие эвристики, заточенные именно под человеческие словари.
и в результате имеет одинаковые кроссворды с теме же самыми сетками и теме же словами, но разными определениями(заданиями) к ним.
Здравствуйте, Sinix, Вы писали:
S>Здравствуйте, novako, Вы писали:
S>Ну дык приведите ваш пример np-полной задачи и как вы её решаете. S>За одно нахождение сверхбольших простых/разложение на множители/дискретные логарифмы вам безопасники памятник поставят. Посмертно (с).
Еще об этом не думал, да и желания думать нет, положительного смысла в этом мало.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Буравчик, Вы писали:
Б>>Я согласен со всем, что написано в сообщении, но не понял, что из этого следует
К>Из этого следует, что у топикстартера может быть сколь угодно революционный эвристический генератор кроссвордов, но по-прежнему экспоненциальный.
В ходе исследований которыми без малого я занимаюсь 10 лет, действительно от экспоненты не уйти, по крайней мера пока что не удалось, ее лишь можно существенно минимизировать. И для решения не общей а реальной задачи вполне приемлемо, а собственно что еще нужно? Если есть возможность решать задачи из жизни за которые деньги платят. В тоже время если например разработать алгоритм который будет эффективно решать задачу составления расписания — согласитесь что это куда перспективнее и нужнее чем кроссворды.
Здравствуйте, Sinix, Вы писали:
S>За одно нахождение сверхбольших простых/разложение на множители/дискретные логарифмы вам безопасники памятник поставят. Посмертно (с)
Именно! Тока сперва еще и помучаем, чтоб другим неповадно было!
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Здравствуйте, novako, Вы писали:
N>Наверное мне удалось найти решение NP-трудных задач. Как утверждает теория это значит что можно решить любую из них. Или по крайней мере в конкретном приложении знаю как свести число перебора вариантов до n^4 или n^5 в отличии от полного перебора например n!. Надеюсь что не ошибся. Писал письма Джонсону, институт Клея, Аарону — не ответа не привета. Вопрос что мне с этим делать? Пока что реализовал для кроссвордов, решил сделать на их составлении бизнес больше ни чего не придумал. А вы уважаемые его к тому же это расскритиковали.мой пост
Здравствуйте, Кодт, Вы писали:
К>Из этого следует, что у топикстартера может быть сколь угодно революционный эвристический генератор кроссвордов, но по-прежнему экспоненциальный.
А может и наоборот. Полиномиальный алгоритм Хачияна хуже чем экспоненциальный симплекс-метод.
Здравствуйте, Sinix, Вы писали:
S>Здравствуйте, novako, Вы писали:
S>Ну дык приведите ваш пример np-полной задачи и как вы её решаете. S>За одно нахождение сверхбольших простых/разложение на множители/дискретные логарифмы вам безопасники памятник поставят. Посмертно (с).
Да нет, почему же посмертно. Мы на него живого памятник поставим
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, novako, Вы писали:
N>>Наверное мне удалось найти решение NP-трудных задач. Как утверждает теория это значит что можно решить любую из них. Или по крайней мере в конкретном приложении знаю как свести число перебора вариантов до n^4 или n^5 в отличии от полного перебора например n!. Надеюсь что не ошибся. Писал письма Джонсону, институт Клея, Аарону — не ответа не привета. Вопрос что мне с этим делать? Пока что реализовал для кроссвордов, решил сделать на их составлении бизнес больше ни чего не придумал. А вы уважаемые его к тому же это расскритиковали.мой пост