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

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

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

Как сообщил «Новому Региону» доктор физико-математических наук, профессор, заведующий кафедрой экономико-математических методов и статистики на факультете вычислительной математики и информатики Анатолий Панюков, с 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 2235 0 Научные открытия
-1
Немецкий школьник сделал открытие в классической механике
Немецкий школьник Шаурийя Рай решил сразу две серьезные математические задачи, участвуя в конкурсе Дрезденского университета. Об этом сообщает издание The Local. Сам конкурс завершился в марте 2012 года, однако только сейчас решение школьника прошло проверку профессиональными математиками. ..
2012-05-24 2415 0 Научные открытия
0
Современная математика оказалась бессильна перед задачей Навье-Стокса
Лауреат Филдсовской медали математик Теренс Тао опубликовал работу, которая доказывает невозможность решения посвященной задаче Навье-Стокса проблемы тысячелетия существующими на настоящий момент средствами. Препринт (pdf) статьи доступен на arXiv.org. Тао попытался формализовать представление многих математиков ..
2014-02-26 2447 0 Научные открытия
1
Математик нашел все паркетные многоугольники
Математик Михаэль Рао из Национального центра научных исследований и Высшей нормальной школы Лиона (Франция) классифицировал все паркетные многоугольники, которыми можно замостить плоскость без пробелов и наложений. Соответствующий препринт доступен на сайте вуза, кратко о нем сообщает Quanta Magazine.В представленном ..
2017-07-14 19247 0 Научные открытия
0
Бабай приблизился к решению «проблемы тысячелетия»
Математик Ласло Бабай из Чикагского университета в США разработал теоретический алгоритм, позволяющий существенно ускорить сравнение графов друг с другом. Исследование ученого связано с проблемой равенства классов P и NP, являющейся одной из «проблем тысячелетия». Об этом сообщает Nature News.Исследование ученого ..
2015-11-20 2627 0 Научные открытия
0
Хиггс оценил вклад советских физиков-теоретиков в Стандартную модель
Двух советских физиков-теоретиков лауреат Нобелевской премии Питер Хиггс (Peter Higgs) назвал причастными к открытию бозона, названного в его честь. Об этом шотландский ученый сообщил в интервью «Газете.Ru». «В 1964 году, когда я описал бозон, помимо меня это сделали ..
2014-09-18 1539 0 Научные открытия
0
Школьник открыл дешевый способ диагностирования рака
Школьник открыл дешевый способ диагностирования рака на ранних стадиях Пятнадцатилетний подросток Джек Андрака нашел новый простой способ лечения рака. Необычная идея пришла мальчику голову так же внезапно, как и Архимеду закон гидростатики: во время урока биологии в школе. Джек ..
2012-08-25 2975 0 Научные открытия
0
Физик имитировал излучение от черной дыры
Ученые подошли вплотную к созданию в лабораторных условиях излучения от черных дыр. Так, Джеффу Штайнхауэру (Jeff Steinhauer) из Израиля с помощью лазера удалось создать квантовый аналог черной дыры и наблюдать излучение, свойства которого во многом схожи с радиацией ..
2014-10-15 1741 0 Научные открытия
0
Генетик оспорил приоритет Дарвина в разработке теории эволюции
Майкл Уил из факультета медицинской и молекулярной генетики Кингс-колледжа в Лондоне сообщил, что шотландец Патрик Мэттью почти на три десятилетия раньше Чарльза Дарвина высказал основные идеи эволюции. Результаты своих исследований автор опубликовал в журнале Biological Journal of the Linnean Society, ..
2015-04-23 5541 0 Научные открытия
1
Представлен обнаруживший гравитационные волны ученый
Первым человеком, зарегистрировавшим гравитационные волны — возмущения пространства-времени, предсказанные сто лет назад создателем общей теории относительности Альбертом Эйнштейном, стал итальянский ученый из Падуи Марко Драго, работающий в Институте гравитационной физики Общества Макса Планка в Ганновере. Об этом ..
2016-02-13 1414 0 Научные открытия
1
Российские полярники готовятся к исследованию древнего антарктического озера
Российские полярники в Антарктиде находятся на пороге крупного открытия - они получат доступ к озеру, законсервированному миллион лет назад. Об этом в интервью сегодняшней "Российской газете" сообщил известный российский полярник, ученый-океанолог Артур Чилингаров. На днях он вылетает в Антарктиду, на станцию "Восток". ..
2012-01-27 1991 1 Научные открытия
0
Лауреаты Нобелевской премии посчитали свое открытие бесполезным
Открытие, за которое физики получат Нобелевскую премию, было сделано случайно. Об этом во вторник, 4 октября, сообщает ТАСС, цитируя одного из лауреатов Дункана Халдейна. Ученый рассказал о том, что он и его коллеги даже не думали, что их исследование может оказаться полезным.На вопрос ..
2016-10-04 1870 0 Научные открытия
0
Падающие атомы проверили закрученность пространства-времени
Физики из университетов Гуаньчжоу и Сунь Ятсена проверили универсальность гравитации по отношению к объектам, обладающим различным спином. С точностью вплоть до десятимиллионных долей авторам удалось показать, что свободное падение для атомов рубидия не зависит от их собственного момента импульса. Этот результат ..
2016-07-09 1873 0 Научные открытия
0
Нобелиат совершил новый научный прорыв спустя пару недель после получения премии
Журнал Science опубликовал статью, в которой рассказывается о новом изобретении Эрика Бетцига (Eric Betzig) — нобелевского лауреата по химии, — которое, по мнению ученого, обладает гораздо большей важностью для науки. 8 октября 2014 года Бетциг совместно с Уильямом Мернером ..
2014-10-27 1968 0 Научные открытия
-1
Теореме Пенроуза о гравитационной сингулярности исполнилось полвека
Теореме Пенроуза о сингулярности черной дыры исполнилось полвека. О знаменитом следствии общей теории относительности (ОТО), вводящем понятие гравитационной сингулярности и ловушечной поверхности, впервые рассказал британский математик и физик Роджер Пенроуз. Об этом напоминает журнал Classical ..
2015-10-02 1615 0 Научные открытия
-1