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

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

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

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

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

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

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

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

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

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

Lenta.ru

Похожие новости:
Физическую «проблему тысячелетия» посчитали неразрешимой
Физики из Великобритании, Испании и Германии посчитали одну из «проблем тысячелетия» (связанную с физикой элементарных частиц) неразрешимой. Результаты своих исследований Тоби Кубитт, Дэвид Гарсия Перес и Майкл Вольф опубликовали в журнале Nature, а кратко о них сообщает Nature News.В ..
2015-12-12 2860 0 Научные открытия
-1
Современная математика оказалась бессильна перед задачей Навье-Стокса
Лауреат Филдсовской медали математик Теренс Тао опубликовал работу, которая доказывает невозможность решения посвященной задаче Навье-Стокса проблемы тысячелетия существующими на настоящий момент средствами. Препринт (pdf) статьи доступен на arXiv.org. Тао попытался формализовать представление многих математиков ..
2014-02-26 3393 0 Научные открытия
1
В Луганске решена одна из задач тысячелетия
Профессор кафедры «Компьютерные системы и сети» Восточноукраинского национального университета имени Владимира Даля Анатолий Плотников предложил и опубликовал в международном научном журнале «Journal of computer science» (8 том, 7 выпуск) вариант решения ранее нерешенной математической задачи «P ..
2012-09-13 3163 0 Научные открытия
-1
Челябинский ученый решил одну из семи неразрешимых задач
Математик из Челябинска Анатолий Панюков нашел решение одной из важнейших задач в современной науке. Как сообщил «Новому Региону» доктор физико-математических наук, профессор, заведующий кафедрой экономико-математических методов и статистики на факультете вычислительной математики и информатики Анатолий Панюков, с 1983 ..
2013-12-16 3662 0 Научные открытия
-1
Российский математик заявил о решении двух проблем Гильберта
Профессор Нижегородского государственного университета имени Николая Лобачевского доктор физико-математических наук Ярослав Сергеев в интервью ТАСС заявил о решении двух проблем Гильберта. Исследования опубликованы в журнале Европейского математического общества EMS Surveys in Mathematical Sciences.Первая проблема, о решении ..
2017-11-28 14065 0 Научные открытия
1
Российские ученые пробурили 4-километровый лед в Антарктиде
После 30 лет бурения российские ученые проникли в подледниковое озеро Восток в Антарктиде, сообщил в понедельник источник в научных кругах. «Вчера на станции Восток в Антарктиде наши ученые на глубине 3,768 тыс. метров завершили бурение и достигли поверхности подледникового озера», - сказал ..
2012-02-6 5825 3 Научные открытия
-1
В ледяной мумии учёные обнаружили самую древнюю кровь
Германо-итальянская группа учёных обнаружила в останках Этци, так называемого Тирольского ледяного человека, который жил приблизительно 5300 лет назад, красные кровяные тельца. Это самый древний биологический материал такого рода.Этци – ледяная мумия, обнаруженная в Альпах на территории Италии ..
2012-05-6 2477 0 Научные открытия
-1
Ученые распутали концы света
Эксперты NASA спешат успокоить: прогнозы, будто 21 декабря 2012 г. мир сгинет в тартарары, лишены всякого основания. Развенчать апокалипсические слухи для аудитории Livescience.com взялся Дон Йоманс, возглавляющий программу NASA по наблюдению за околоземными объектами. Всем, кто переживает из-за окончания календаря ..
2011-12-13 21962 96 Научные открытия
0
Подлёдное озеро Антарктики вскрыто: российские полярники ждут встречи с фантастическими формами жизни
Российские учёные первыми в мире добрались до вод озера Восток, которые были законсервированы подо льдами Антарктики в течение миллионов лет. В "чужеродной" среде они надеются обнаружить невиданные науке организмы, которые за несколько тысячелетий могли эволюционировать в необычные формы ..
2012-02-8 3045 0 Научные открытия
1
Шарлатаны атакуют: попытка легализации лженауки
Недавно российские лжеученые объявили о старте нового шарлатанского проекта –  выпуске псевдо рецензируемого издания «Журнал формирующихся направлений науки», само название которого выдает намерение примазаться к науке. 500 миллионов рублей в конце 80-х годов –  ..
2013-06-16 2223 1 Научные открытия
0
Внутри протона
Завершено 23-летнее исследование адронной частицы Коллаборации HERA (Hadron-Electron Ring Accelerator) из крупнейшего в Германии центра физики элементарных частиц DESY (Deutsches Elektronen-Synchrotron) завершили 23-летние исследования внутренней структуры и свойств протона. О результатах своей работы ученые ..
2015-07-12 8200 0 Научные открытия
-1
Жизнь после жизни: что останется?
Сегодня каждый из нас занят своими насущными проблемами – учебой, работой, наукой, политикой, созданием семьи и прочими рутинными делами. И никто из нас не задумывается о том, что в суете проблем каждый из нас, пусть по-своему, творит историю. Потому как именно такими ..
2012-03-11 1750 0 Научные открытия
0
Решена одна из старейших и сложнейших математических задач
Схематическое разбиение нескольких первых четных чисел в сумму простых. В середине мая 2013 года математик из Перу, в настоящее время работающий во Франции, Харальд Хельфготт выложил в архив препринтов Корнельского университета статью «Большие дуги для теоремы Гольдбаха». Эта статья ..
2013-06-18 4611 0 Научные открытия
0
Никола Тесла: великий Шаман
Вклад Николы Теслы в хай-тек двадцатого века сложно переоценить. На его открытиях построена вся технология двадцатого столетия. Именно его работа сделала возможным появление современной электроники. И если хотя бы половина из того, о чем говорят его многочисленные поклонники, Никола Тесла действительно ..
2013-03-23 2890 0 Научные открытия
0
Десять научных сенсаций года
Вода на Марсе, фотографии Плутона, самый древний предок человека, протезы и коптеры, управляемые силой мысли, теплокровные динозавры, вакцина против вируса Эбола, непобедимый суперантибиотик нового поколения… Десять самых сенсационных научных открытий 2015 года ..
2015-12-28 4087 0 Научные открытия
-1