Бабай приблизился к решению «проблемы тысячелетия»

Бабай приблизился к решению «проблемы тысячелетия»

Математик Ласло Бабай из Чикагского университета в США разработал теоретический алгоритм, позволяющий существенно ускорить сравнение графов друг с другом. Исследование ученого связано с проблемой равенства классов P и NP, являющейся одной из «проблем тысячелетия». Об этом сообщает Nature News.

Исследование ученого относится к теории графов и посвящено сравнению изоморфных (сохраняющих структуру обратимых отображений) графов (некоторого набора вершин и связей между ними). Ученый показал, что проблема изоморфизма графов (перенумерации вершин одного графа для получения другого), связанная с возможностью существования доказывающего изоморфность двух графов алгоритма, может быть решена.

Положение вершин и связей между ними в графе определяется матрицей смежности. В случае если два графа изоморфны друг другу, существует перестановка, которая позволяет трансформировать матрицу смежности одного графа в матрицу смежности другого графа. Сложность решения этой задачи сводится к нахождению эффективного алгоритма, реализующего такую процедуру.

У изоморфных графов существуют инварианты — одинаковые для них числовые характеристики (например, число вершин). Вычисление полного инварианта графа (всех его инвариантов, перечисления которых необходимо и достаточно для доказательства его изоморфности другому графу) за полиномиальное время остается нерешенной задачей современной математики.

Последние успехи в этом направлении были сделаны в 1983 году. Бабай изложил основные моменты своей работы в двух лекциях, а присутствующие на них эксперты в области теории графов пока не нашли ошибок в рассуждениях ученого. Между тем окончательной верификации в математическом сообществе его работа пока не получила.

Метод математика основывается на предыдущих результатах и ищет симметрии графа, позволяющие переименовать его вершины. Реализация алгоритма происходит в несколько этапов, в каждом из которых происходит упрощение задачи за счет уменьшения количества вершин, которые необходимо переименовать, а также использует алгоритм Джонсона и рекурсию.

Работа Бабая вводит новый и работающий быстрее предыдущих алгоритм, который относится к классу NP-алгоритмов (возможность их работы можно проверить за полиномиальное время), а не классу P-алгоритмов (их время работы полиномиально зависит от размера входных данных).

Проблема равенства классов P и NP сформулирована как одна из семи задач тысячелетия, за решение которой Математический институт Клэя обещает премию в миллион долларов. В случае если исследования Бабая окажутся верными, это может означать существенный прогресс в математике.

Lenta.ru

Похожие новости:
Физическую «проблему тысячелетия» посчитали неразрешимой
Физики из Великобритании, Испании и Германии посчитали одну из «проблем тысячелетия» (связанную с физикой элементарных частиц) неразрешимой. Результаты своих исследований Тоби Кубитт, Дэвид Гарсия Перес и Майкл Вольф опубликовали в журнале Nature, а кратко о них сообщает Nature News.В ..
2015-12-12 1725 0 Научные открытия
-1
Челябинский ученый решил одну из семи неразрешимых задач
Математик из Челябинска Анатолий Панюков нашел решение одной из важнейших задач в современной науке. Как сообщил «Новому Региону» доктор физико-математических наук, профессор, заведующий кафедрой экономико-математических методов и статистики на факультете вычислительной математики и информатики Анатолий Панюков, с 1983 ..
2013-12-16 2494 0 Научные открытия
-1
Современная математика оказалась бессильна перед задачей Навье-Стокса
Лауреат Филдсовской медали математик Теренс Тао опубликовал работу, которая доказывает невозможность решения посвященной задаче Навье-Стокса проблемы тысячелетия существующими на настоящий момент средствами. Препринт (pdf) статьи доступен на arXiv.org. Тао попытался формализовать представление многих математиков ..
2014-02-26 2137 0 Научные открытия
1
В Луганске решена одна из задач тысячелетия
Профессор кафедры «Компьютерные системы и сети» Восточноукраинского национального университета имени Владимира Даля Анатолий Плотников предложил и опубликовал в международном научном журнале «Journal of computer science» (8 том, 7 выпуск) вариант решения ранее нерешенной математической задачи «P ..
2012-09-13 1987 0 Научные открытия
-1
В Китае сделано новое открытие о нейтрино
Международная исследовательская группа, работающая в лаборатории по изучению нейтрино при Даяваньской АЭС в Южном Китае,  опубликовала первые результаты открытия относительно последней и самой неуловимой части давней головоломки: как нейтрино, по видимости, могут исчезать, когда они двигаются.Удивительное открытие приоткрыло путь ..
2012-03-16 2822 3 Научные открытия
-1
Найден способ вернуть зрение слепым
Физиологам из Стэнфордского университета удалось частично восстановить зрение у мышей с разорванными глазными нервами. Для этого был применен комбинированный подход, включающий как визуальную стимуляцию, так и применение химических веществ. Статья с описанием эксперимента опубликована в Nature Neuroscience.В глазах большинства животных ..
2016-07-12 1621 0 Научные открытия
1
Учёным удалось создать графеновые квантовые точки
Группа учёных из Канзасского государственного университета (Kansas State University) разработала новый метод, позволяющий открыть путь к решению давнейшей проблемы в производстве графеновых квантовых точек при большой плотности с регулируемыми размерами и формами, сообщает «PC-News.info». Новый метод, разработанный ..
2012-05-21 1496 0 Научные открытия
-1
Российский математик заявил о решении двух проблем Гильберта
Профессор Нижегородского государственного университета имени Николая Лобачевского доктор физико-математических наук Ярослав Сергеев в интервью ТАСС заявил о решении двух проблем Гильберта. Исследования опубликованы в журнале Европейского математического общества EMS Surveys in Mathematical Sciences.Первая проблема, о решении ..
2017-11-28 2724 0 Научные открытия
1
В Японии прекратили «революционные исследования» стволовых клеток
В японском Институте физико-химических исследований (RIKEN) сообщили о прекращении «революционных исследований» стволовых клеток. Об этом сообщает издание The Japan Times. К такому решению специалисты пришли после того, как автор работы о так называемых STAP-клетках Харуко Обоката не подтвердила их существование. ..
2014-12-22 2231 0 Научные открытия
-2
Российские ученые пробурили 4-километровый лед в Антарктиде
После 30 лет бурения российские ученые проникли в подледниковое озеро Восток в Антарктиде, сообщил в понедельник источник в научных кругах. «Вчера на станции Восток в Антарктиде наши ученые на глубине 3,768 тыс. метров завершили бурение и достигли поверхности подледникового озера», - сказал ..
2012-02-6 4346 3 Научные открытия
-1
Объявлено о самом объемном доказательстве в математике
Ученые из США и Великобритании заявили о крупнейшем по объему занятой компьютерной памяти доказательстве в истории математики. Препринт с исследованием опубликован на сайте arXiv.org, кратко о нем сообщает издание Nature.Для решения булевой проблемы пифагоровых троек специалисты использовали суперкомпьютер Stampede Техасского ..
2016-05-29 1439 0 Научные открытия
-1
В ледяной мумии учёные обнаружили самую древнюю кровь
Германо-итальянская группа учёных обнаружила в останках Этци, так называемого Тирольского ледяного человека, который жил приблизительно 5300 лет назад, красные кровяные тельца. Это самый древний биологический материал такого рода.Этци – ледяная мумия, обнаруженная в Альпах на территории Италии ..
2012-05-6 1521 0 Научные открытия
-1
Физики вывели квантовую механику из полевой теории струн
Американские физики-теоретики продемонстрировали возможность получения квантовомеханических соотношений из специального случая струнной теории поля (полевой теории струн). Результаты своих исследований авторы опубликовали в журнале Physics Letters, а кратко с ними можно ознакомиться на сайте Университета Южной ..
2014-11-05 1824 0 Научные открытия
1
Ученые провели опыты над фотонами света
До недавнего времени рекордное количество запутанных квантовых измерений фотонов равнялось 11, но группе учёных из Institute for Quantum Optics and Quantum Information под руководством Антона Зеилингера и Марио Крена удалось увеличить данный рекорд почти в 10 раз. Их работа поможет в обеспечении ..
2014-04-07 1764 0 Научные открытия
-3
Цель Большого адронного коллайдера - скрыть правду от народа
Основная цель Большого адронного коллайдера (БАК) - скрыть от народа правду о существовании эфира. БАГ это, самый мощный в мире ускоритель частиц, построенный в тоннеле под землей на глубине примерно сотни метров на границе Франции и Швейцарии, недалеко от Женевы, ..
2013-07-25 1971 1 Научные открытия
-1