Комментарии участников:
А если серьёзно — доказательство на бочку или не хер пиздеть. Где ссылка на статью с алгоритмом решения?
падают вроде из-за Китая, а может просто коррекция… в любом случае менее чем 2 месяца назад курс был в районе 200$ за биткоин, а сейчас более 700$
Это невозможно!!! Perpetum mobile или «академик Петрик».
Моя тема. Computational complexity. Лет 10 назад. Даже видел САМОГО Левина, это чувак, нашенский, с 70х живет в штатах, один из постановщиков этой темы.
Вкратце так, здесь упомянули NP-полные задачи (на английском NP-Complete), так это подмножество NP задач связанных друг с другом полиномиальной редукцией, т.е. это можно представить себе в виде цепочки, так что решив одну из них, любую, за полиномиальное время можно решить все, так как переход от одной задачи к другой — берет полиномиальное вычислительное время. То есть транзитивно — полиномиальное решение.
Года до 90 это был PhD — построить такую редукцию от доказанной проблемы из NPC к обсуждаеимой, сегодня — статейка максимум. Не интересно.
Одна из известных задач — «задача комивояжора».
Так же задачи из области криптографии.
Короче то что P не равно NP понятно всем, но формального доказательства нет и в принципе невозможно трудно представимо как это доказать. Есть даже фонд, еще с 70х, когда это были очень большие деньги — лимон баксов тому, кто докажет это неравенство.
Моя тема. Computational complexity. Лет 10 назад. Даже видел САМОГО Левина, это чувак, нашенский, с 70х живет в штатах, один из постановщиков этой темы.
Вкратце так, здесь упомянули NP-полные задачи (на английском NP-Complete), так это подмножество NP задач связанных друг с другом полиномиальной редукцией, т.е. это можно представить себе в виде цепочки, так что решив одну из них, любую, за полиномиальное время можно решить все, так как переход от одной задачи к другой — берет полиномиальное вычислительное время. То есть транзитивно — полиномиальное решение.
Года до 90 это был PhD — построить такую редукцию от доказанной проблемы из NPC к обсуждаеимой, сегодня — статейка максимум. Не интересно.
Одна из известных задач — «задача комивояжора».
Так же задачи из области криптографии.
Короче то что P не равно NP понятно всем, но формального доказательства нет и в принципе невозможно трудно представимо как это доказать. Есть даже фонд, еще с 70х, когда это были очень большие деньги — лимон баксов тому, кто докажет это неравенство.
Поискал Панюкова в журнале www.mathnet.ru/php/journal.phtml?jrnid=at&wshow=details&option_lang=rus — автоматика и телемеханика. Просто «механики» нет как таковой. В архиве 2013 года публикации нет ((
Хотя там он публиковался www.mathnet.ru/php/person.phtml?option_lang=rus&personid=30278 посмотри пож.
может я что не понял?
Хотя там он публиковался www.mathnet.ru/php/person.phtml?option_lang=rus&personid=30278 посмотри пож.
может я что не понял?
Он занимается оптимизациями.
Это — для практического подхода к NP сложным задачам.
Например — составление расписания ;)
Или тот же коммивояжер… в сетях применимость огромнейшая.
Перебор всех вариантов и нахождения кратчайшего (оптимального) решения займет миллион лет при всего сотнях хорошо связанных точек даже если все компы мира будут ее решать ;) степенная сложность, хули.
Суть — нахождения приближённого полиномиального (разрешимого за приемлемое время) решения.
Степень приближенности к оптимуму — суть дела.
Это — для практического подхода к NP сложным задачам.
Например — составление расписания ;)
Или тот же коммивояжер… в сетях применимость огромнейшая.
Перебор всех вариантов и нахождения кратчайшего (оптимального) решения займет миллион лет при всего сотнях хорошо связанных точек даже если все компы мира будут ее решать ;) степенная сложность, хули.
Суть — нахождения приближённого полиномиального (разрешимого за приемлемое время) решения.
Степень приближенности к оптимуму — суть дела.
Панюков Анатолий Васильевич (род. в 1951 г.) Доктор физико-математических наук, профессор, заведующий кафедрой экономико-математических методов и статистики на факультете вычислительной математики и информатики, член ассоциации математического программирования, ученый секретарь Научно-методического совета по математике Министерства образования и науки РФ (Челябинское отделение), член Научно-методического совета Территориального органа Федеральной службы государственной статистики по Челябинской области, член диссертационных советов в Южно-Уральском и Пермском государственных университетах. Автор более 200 научных и учебных публикаций и более 20 изобретений. Руководитель научного семинара «Доказательные вычисления в экономике, технике, естествознании», работа которого поддержана грантами РФФИ, Министерства образования и Международного научно-технического центра. Им подготовлено семь кандидатов и два доктора наук. Имеет звания «Заслуженный работник высшей школы РФ» (2007), «Почетный работник высшего профессионального образования» (2001), «Изобретатель СССР» (1979), награжден медалью Минвуза СССР (1979) и Почётной грамотой Губернатора Челябинской области.
Блин, я у него учился )))… в ЮУрГУ )))…
Что за х… реновина стала творится последнее время на news2.ru?
Ну, явная же хрень, а не новость. Доступная в своей хреновости не только тем, кто разбирается, но даже тем, кто что-то где-то слышал о проблеме P=NP.
Почему подобное стало регулярно выходить в топ?
Почему верхние 3-4 новости на главной news2.ru теперь приходится всегда проматывать, у них желтушность так зашкаливает, что газете Жизнь еще учиться и учиться?
Что произошло с ресурсом, руководство поменялось, что-ли?
Ну, явная же хрень, а не новость. Доступная в своей хреновости не только тем, кто разбирается, но даже тем, кто что-то где-то слышал о проблеме P=NP.
Почему подобное стало регулярно выходить в топ?
Почему верхние 3-4 новости на главной news2.ru теперь приходится всегда проматывать, у них желтушность так зашкаливает, что газете Жизнь еще учиться и учиться?
Что произошло с ресурсом, руководство поменялось, что-ли?
почему хрень-то? 
www.itar-tass.com/ural-news/837298 на сколько я понял сейчас на стадии проверки «компетентными структурами»
www.itar-tass.com/ural-news/837298 на сколько я понял сейчас на стадии проверки «компетентными структурами»
Дело в том, что это не первое доказательство P=NP, и даже не десятое. И даже не сотое.
С тех пор как теорему Ферма решили, все мат-фрики в P=NP ударились, каждый лох с двумя курсами вышки свое доказательство на полях тетрадки пишет. Вот первая сотня тут приведена. Так что челябинскому математику придется в очередь встать, подождать маленько, покуда «компетентные структуры» до его доказательства доберутся.
В таких условиях писать новость с заголовком «Челябинский ученый решил одну из семи неразрешимых задач тысячелетия Он доказал равенство классов сложности Р и NP» это даже не желтуха. Это чернуха-порнуха полнейшая.
С тех пор как теорему Ферма решили, все мат-фрики в P=NP ударились, каждый лох с двумя курсами вышки свое доказательство на полях тетрадки пишет. Вот первая сотня тут приведена. Так что челябинскому математику придется в очередь встать, подождать маленько, покуда «компетентные структуры» до его доказательства доберутся.
В таких условиях писать новость с заголовком «Челябинский ученый решил одну из семи неразрешимых задач тысячелетия Он доказал равенство классов сложности Р и NP» это даже не желтуха. Это чернуха-порнуха полнейшая.
Поддерживаю, как то не верится, что столь занятый человек мог заниматься такой ерундой. Не до того ему.
Возможно, что писаки не поняли чего он там решил.
Для NP сложных задач пишут всякие приближённые алгоритмы, вероятностные и т.д. с ограниченной решимостью, находят всякие гранитные условия, оптимизации, комбинаторика — это огромная область Computer Science, и кстати, из-за связи с криптографией очень даже неплохо финансируемая и т.д. Возможно, что Панюков что-то в этой области и придумал, какой нибудь приближённый алгоритм для какой-нибудь NP-C задачи с чуть лучшим ratio, а они услышали звон, не зная где он и давай строчить «скупы», типа P=NP бугага.
Для NP сложных задач пишут всякие приближённые алгоритмы, вероятностные и т.д. с ограниченной решимостью, находят всякие гранитные условия, оптимизации, комбинаторика — это огромная область Computer Science, и кстати, из-за связи с криптографией очень даже неплохо финансируемая и т.д. Возможно, что Панюков что-то в этой области и придумал, какой нибудь приближённый алгоритм для какой-нибудь NP-C задачи с чуть лучшим ratio, а они услышали звон, не зная где он и давай строчить «скупы», типа P=NP бугага.
Вроде хороший дискурс прошел. Тему-то прояснили. по крайней мере для меня, далекого от математики человека. Всем участни кам огромное спасибо!
Отдельно для![sly2m]()
sly2m: А причем здесь руководство ресурса. Его же нет — есть просто наши ответственные коллеги. Новость вышла в ТОП из-за общего решения — бекоз хотелось понять, что это было. Заголовок — как в источнике, и, надо признаться, я не считаю ее желтой до сих пор. Просто погоня за научной сенсацией.
Сам Панюков не хрен с горы, а известный математик — вот данные академии Гугла Так что народ голосовал не на пустом месте. И всяко эта новость лучше политики, от которой не уйдешь, но которой заниматься конкретно противно.
Отдельно для
sly2m: А причем здесь руководство ресурса. Его же нет — есть просто наши ответственные коллеги. Новость вышла в ТОП из-за общего решения — бекоз хотелось понять, что это было. Заголовок — как в источнике, и, надо признаться, я не считаю ее желтой до сих пор. Просто погоня за научной сенсацией. Сам Панюков не хрен с горы, а известный математик — вот данные академии Гугла Так что народ голосовал не на пустом месте. И всяко эта новость лучше политики, от которой не уйдешь, но которой заниматься конкретно противно.
Если он не хрен с горы, то должен был уже давно сделать заявление, что журналюги врут, и он ничего такого не заявлял (по крайней мере того, что пизданули в заголовке статьи).
Раз молчит — значит он кто угодно (хвастун, идиот, трус, чиновник, администратор, пиарщик...), но никак не ученый.
Раз молчит — значит он кто угодно (хвастун, идиот, трус, чиновник, администратор, пиарщик...), но никак не ученый.
а вот и не молчит. Вот первоисточник видать 
hornews.ru/news/last_news/chelyabinskiy_matematik_reshil_odnu_iz_zadach_tyisyacheletiya.html — сам хвалится. Рекомендую для анализа.
hornews.ru/news/last_news/chelyabinskiy_matematik_reshil_odnu_iz_zadach_tyisyacheletiya.html — сам хвалится. Рекомендую для анализа.
Типичный совковый Выбегалло-соавтор, выучивший пару слов из работы и щедро приправивший свой идиотизм заявлениями о пользе для народного хозяйства. Внутре у ней значиццо неонка.
Потому что даже если бы он доказал, что существует полиномиальный алгоритм для какой-то NP-полной задачи (что было бы ОЧЕНЬ круто), то из этого ещё не следует N=NP.
Использовать эпитет «сложная» для NP-полной задачи, это уже само по себе бред.
Типа бывают простые NP-полные задачи.
Вся суть NP-полноты — во взаимной полиномиальной сводимости задач друг к другу.
Поэтому не бывает более или менее сложных NP-полные задач.
При этом назвать саму задачу математик постеснялся.
Нормальный подход подразумевает:
— строго определить задачу
— привести алгоритм решения в общем случае
— доказать, что этот алгоритм детерминировано завершается за полиномиальное время
— доказать, что некая уже доказанная NP полная задача сводится к нашей для любого допустимого набора входных данных
Если это честно проделать, то мы автоматически имеем полиномиальный алгоритм решения любой NP-полной задачи. В частности, например, для задачи коммивояжера.
Но даже это не гарантирует равенство N=NP, так как, например, задача факторизации целых чисел
очевидно NP, но совсем не факт, что NPC.
useless-faq.livejournal.com/13955550.html?thread=446971614&
Математик сообщил, что он доказал полиномиальную разрешимость одной из сложных NP- полных задач.
Использовать эпитет «сложная» для NP-полной задачи, это уже само по себе бред.
Типа бывают простые NP-полные задачи.
Вся суть NP-полноты — во взаимной полиномиальной сводимости задач друг к другу.
Поэтому не бывает более или менее сложных NP-полные задач.
При этом назвать саму задачу математик постеснялся.
Нормальный подход подразумевает:
— строго определить задачу
— привести алгоритм решения в общем случае
— доказать, что этот алгоритм детерминировано завершается за полиномиальное время
— доказать, что некая уже доказанная NP полная задача сводится к нашей для любого допустимого набора входных данных
Если это честно проделать, то мы автоматически имеем полиномиальный алгоритм решения любой NP-полной задачи. В частности, например, для задачи коммивояжера.
Но даже это не гарантирует равенство N=NP, так как, например, задача факторизации целых чисел
очевидно NP, но совсем не факт, что NPC.
useless-faq.livejournal.com/13955550.html?thread=446971614&Давайте по пунктам:
— Факторизация — очевидно NP. Так как если «волшебное недетерменированное устройство» даст разложение, его можно проверить на корректность за полиномиальное время.
— Факторизация — не NP-полная задача. Нельзя доказать ее эквивалентность другим известным NP-полным задачам (SAT, travelling salesman, etc). И нельзя доказать, что любая задача из NP сводится к ней.
— Я специально отметил, что фраза выше — не строгое доказательство. Это просто грубое пояснение «на пальцах», почему факторизация — не NP-полная задача, в чем ее «тонкое» отличие, на каких идеях строятся «более эффективные» алгоритмы для этой задачи.
— Для факторизации есть полиномиальный квантовый алгоритм (построен прототип), для NP-полных задач — нет. Доказательства отсутствия такового для NP-полных задач нет, но предпосылок к его обнаружению тоже нет.
— Для факторизации нет известного полиномиального «классического» алгоритма (машины Тьюринга), для NP-полных задач тоже нет.
— По этим причинам из того, что нам уже известен квантовый алгоритм факторизации за полиномиальное время, не следует, что квантовые компьютеры могут вдруг решать все NP-полные задачи.
Более расширенное и строгое пояснение (но все еще «на пальцах») можно почитать тут:
www.scottaaronson.com/democritus/lec6.html
Жесть, почему это на главной? Где текст доказательства? Оно должно быть настолько сложным, что на проверку уйдёт несколько месяцев.
Очередное «доказательство» для СМИ, как у многочисленныхферматистах и прочих математических фриках.
Очередное «доказательство» для СМИ, как у многочисленных
ферматистах и прочих математических фриках. 
