Челябинский ученый решил одну из семи неразрешимых задач

Челябинский ученый решил одну из семи неразрешимых задач

Математик из Челябинска Анатолий Панюков нашел решение одной из важнейших задач в современной науке.

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

Данная задача является одной из важнейших в теории алгоритмов, и одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в 1 миллион долларов США.

В чем суть проблемы равенства классов Р и NP? Есть некий класс задач, для которых можно быстро находить решение (за полиномиальное время), его называют P классом. А есть класс задач, для которых можно быстро проверить правильность их решения, при этом создать алгоритм решения очень сложно – это NP класс. Пока не известно, можно ли, хотя бы в теории, найти такой алгоритм, по которому возможно так же быстро находить решение поставленной задачи, как и проверять его правильность.

Равенство классов означает, что задачи класса NP можно будет решать за полиномиальное время, что сулит огромную выгоду в скорости вычислений. Сейчас самые сложные задачи из класса NP (так называемые NP-полные задачи) можно решить за экспоненциальное время, что считается неприемлемым с практической точки зрения.

По словам челябинского ученого окончательные результаты исследования пока не опубликованы, но своим решением задачи равенства классов P и NP он уже делился с российскими и зарубежными коллегами. Так, свое доказательство Панюков представил на международной конференции в Черногории, а также в Институте математики и механики УрО РАН и в журнале «Автоматика и механика».

Математик сообщил, что он доказал полиномиальную разрешимость одной из сложных NP- полных задач.

Ученый собирается представить, свое решение и в Математический институт Клэя, но для этого необходимо хорошо подготовиться. По словам Анатолия Панюкова, на сегодняшний день в мире существует более 100 вариантов решения данной математической проблемы. Примечательно, что большинство ученых склоняется к тому что классы Р и NP не равны. На данный момент пока ни одно из решений официально не признано.

Отметим, из 7 задач тысячелетия сегодня решена только одна – гипотеза Пуанкаре. В 2002 году российский ученый Григорий Перельман опубликовал серию работ, из которых следует справедливость гипотезы. За это в 2006 году ему была присуждена международная премия «Медаль Филдса» («За вклад в геометрию и его революционные идеи в изучении геометрической и аналитической структуры потока Риччи»). От премии в 1 миллион долларов США ученый отказался.

Источник: nr2.ru

Похожие новости:
В Луганске решена одна из задач тысячелетия
Профессор кафедры «Компьютерные системы и сети» Восточноукраинского национального университета имени Владимира Даля Анатолий Плотников предложил и опубликовал в международном научном журнале «Journal of computer science» (8 том, 7 выпуск) вариант решения ранее нерешенной математической задачи «P ..
2012-09-13 2405 0 Научные открытия
-1
Современная математика оказалась бессильна перед задачей Навье-Стокса
Лауреат Филдсовской медали математик Теренс Тао опубликовал работу, которая доказывает невозможность решения посвященной задаче Навье-Стокса проблемы тысячелетия существующими на настоящий момент средствами. Препринт (pdf) статьи доступен на arXiv.org. Тао попытался формализовать представление многих математиков ..
2014-02-26 2650 0 Научные открытия
1
Немецкий школьник сделал открытие в классической механике
Немецкий школьник Шаурийя Рай решил сразу две серьезные математические задачи, участвуя в конкурсе Дрезденского университета. Об этом сообщает издание The Local. Сам конкурс завершился в марте 2012 года, однако только сейчас решение школьника прошло проверку профессиональными математиками. ..
2012-05-24 2572 0 Научные открытия
0
Падающие атомы проверили закрученность пространства-времени
Физики из университетов Гуаньчжоу и Сунь Ятсена проверили универсальность гравитации по отношению к объектам, обладающим различным спином. С точностью вплоть до десятимиллионных долей авторам удалось показать, что свободное падение для атомов рубидия не зависит от их собственного момента импульса. Этот результат ..
2016-07-09 2072 0 Научные открытия
4
Физическую «проблему тысячелетия» посчитали неразрешимой
Физики из Великобритании, Испании и Германии посчитали одну из «проблем тысячелетия» (связанную с физикой элементарных частиц) неразрешимой. Результаты своих исследований Тоби Кубитт, Дэвид Гарсия Перес и Майкл Вольф опубликовали в журнале Nature, а кратко о них сообщает Nature News.В ..
2015-12-12 2171 0 Научные открытия
-1
Бабай приблизился к решению «проблемы тысячелетия»
Математик Ласло Бабай из Чикагского университета в США разработал теоретический алгоритм, позволяющий существенно ускорить сравнение графов друг с другом. Исследование ученого связано с проблемой равенства классов P и NP, являющейся одной из «проблем тысячелетия». Об этом сообщает Nature News.Исследование ученого ..
2015-11-20 3452 0 Научные открытия
0
Создана первая масштабируемая реализация квантового алгоритма
Физики из Массачусетского технологического института в США и Инсбрукского университета в Австрии создали квантовый компьютер, который впервые допускает масштабирование при реализации квантового алгоритма Питера Шора. Исследование ученых опубликовано в журнале Science.Ученые спроектировали и построили квантовый компьютер из пяти атомов ..
2016-03-04 1506 0 Научные открытия
3
Ядро Земли оказалось богато водородом
Геофизики из Японии и России пришли к выводу, что ядро Земли богато серой, кремнием и водородом. Результаты исследований ученые опубликовали в журнале Science Advances.Ядро планеты состоит главным образом из железа, а главными кандидатами на более легкие элементы в центре Земли ..
2016-02-29 1924 0 Научные открытия
2
Физики из МГУ создали сверхбыстрый фотонный переключатель
Физики из России и Австралии создали сверхбыстрый фотонный переключатель, работающий на кремниевых наноструктурах. Устройство может стать основой компьютеров будущего и позволить передавать данные с огромной скоростью. Результаты своих исследований авторы опубликовали в журнале Nano Letters, а кратко ..
2015-10-18 1848 0 Научные открытия
0
Возбуждение электронов записали на видео
Инженеры из Массачусетского технологического университета записали на видео возбуждение электронов, происходящее на поверхности топологических изоляторов. Работа опубликована в журнале Physical Review Letters, кратко ее содержание можно прочитать на сайте университета. Записать динамику электронного феномена, который длится не более 5 пикосекунд (10-12секунд) ..
2012-09-19 1453 0 Научные открытия
0
Ученые получили снимок тени атома вещества
Ученые из Университета Гриффита впервые в истории смогли сфотографировать тень, которую отбрасывает всего один атом вещества.Атом столь невелик, что его тень можно зафиксировать только в одном положении. Если микроскоп отклонится от него всего на одну миллиардную долю ..
2012-07-6 1694 0 Научные открытия
0
В таянии антарктического льда виноват теплый океан
Большая часть таяния льда в Антарктиде происходит в результате наличия теплой воды на окраинах континента.Ученые использовали спутниковый лазер для измерения истончения шельфовых ледников. В ходе анализа они обнаружили, что в сокращение шельфовых льдов «нельзя обвинять только повышенную температуру ..
2012-04-26 1441 0 Научные открытия
0
Раскрыт механизм человеческой памяти
Исследователи из Массачусетской общей больницы под руководством Джошуа Роффмана (Joshua Roffman) выяснили, как дофаминовые рецепторы обеспечивают функционирование рабочей или оперативной памяти в мозге людей. В частности, было показано, что дофамин перенаправляет когнитивные ресурсы на поддержание необходимых функций мозга. ..
2016-06-05 2565 0 Научные открытия
0
Найдено безболезненное средство против камней в почках
Американские исследователи из Университета в Хьюстоне выяснили, что натуральный растительный экстракт способен растворить оксалат кальция — компонент камней в почках человека. О своем открытии ученые рассказали в статье, опубликованной в журнале Nature.Химики определили, что соединение, называемое гидроксицитратом, является эффективным ..
2016-08-09 3407 0 Научные открытия
0
Ученые создали искусственные тромбоциты
Ученые из  Калифорнийского университета в Санта-Барбаре (UC Санта-Барбара) создали синтетические тромбоциты, компоненты крови, которые препятствуют чрезмерному кровотечению и обладают способностью быстро заживлять раны,сообщает«WordScience.org». Уникальные физические и биохимические свойства тромбоцитов играют важную роль в выполнении сложных биологических ..
2012-06-5 1401 0 Научные открытия
0