LAT Чт, 3. Апреля Завтра: Daira, Dairis
Доступность

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

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

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

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

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

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

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

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

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

Загрузка
Загрузка
Загрузка

Зато купили отели в Хорватии… В Украине скандал с закупками продуктов для армии: украдено 17 млн. USD

Сегодня, 2 апреля, украинские антикоррупционные органы огласили обвинительное заключение по делу о коррупции, связанному с закупкой Министерством обороны продовольствия по завышенным ценам в 2022-2023 годах, сообщает la.lv со ссылкойн на Kyiv Independent.

Сегодня, 2 апреля, украинские антикоррупционные органы огласили обвинительное заключение по делу о коррупции, связанному с закупкой Министерством обороны продовольствия по завышенным ценам в 2022-2023 годах, сообщает la.lv со ссылкойн на Kyiv Independent.

Читать
Загрузка

Договорятся или нет? Посланник Путина едет в Вашингтон, но есть нюансы

Администрация США продолжает искать способы добиться обещанного Дональдом Трампом мира в Украине: на этой неделе, по сведениям из нескольких источников, в Вашингтон прилетит представитель президента России Кирилл Дмитриев. Тем временем в мировой прессе продолжают появляться «утечки» информации о том, что администрация Трампа крайне недовольна нежеланием Москвы прекратить огонь.

Администрация США продолжает искать способы добиться обещанного Дональдом Трампом мира в Украине: на этой неделе, по сведениям из нескольких источников, в Вашингтон прилетит представитель президента России Кирилл Дмитриев. Тем временем в мировой прессе продолжают появляться «утечки» информации о том, что администрация Трампа крайне недовольна нежеланием Москвы прекратить огонь.

Читать

Лидером списка «Sarauj, Latgale!» в Даугавпилсе будет мэр Элксниньш, в Резекне — депутат Рижской думы Морозов

Лидером кандидатского списка партии "Sarauj, Latgale!" на выборах в Даугавпилсе будет действующий мэр города Андрей Элксниньш, в Резекне - депутат Рижской думы Андрис Морозов, свидетельствуют данные Центральной избирательной комиссии.

Лидером кандидатского списка партии "Sarauj, Latgale!" на выборах в Даугавпилсе будет действующий мэр города Андрей Элксниньш, в Резекне - депутат Рижской думы Андрис Морозов, свидетельствуют данные Центральной избирательной комиссии.

Читать

Пенсии повышаются? Подробнее — о новом порядке начисления и выплаты пенсий.

Получатели пенсий по возрасту заметили, что в этом году пенсии немного подросли. Какова причина и следует ли ждать дальнейших шагов в сторону увеличения государственных пенсий? Такие вопросы задают читатели. Государственное агентство социального страхования (VSAA) -- о новом порядке начисления и выплаты пенсий.

Получатели пенсий по возрасту заметили, что в этом году пенсии немного подросли. Какова причина и следует ли ждать дальнейших шагов в сторону увеличения государственных пенсий? Такие вопросы задают читатели. Государственное агентство социального страхования (VSAA) -- о новом порядке начисления и выплаты пенсий.

Читать

Европол накрыл крупнейшую в мире платформу для педофилов: двое задержанных из Латвии

Kidflix, одна из крупнейших в мире платформ для педофилов, была закрыта в ходе международной операции против сексуальной эксплуатации детей. Расследование проводилось при поддержке Европола и возглавлялось Баварской уголовной полицией и Баварским центральным управлением по расследованию киберпреступлений. В операции приняли участие более 35 стран мира. Управление Госполиции по борьбе с киберпреступностью задержало в Латвии двоих фигурантов уголовного дела, сообщает Госполиция.

Kidflix, одна из крупнейших в мире платформ для педофилов, была закрыта в ходе международной операции против сексуальной эксплуатации детей. Расследование проводилось при поддержке Европола и возглавлялось Баварской уголовной полицией и Баварским центральным управлением по расследованию киберпреступлений. В операции приняли участие более 35 стран мира. Управление Госполиции по борьбе с киберпреступностью задержало в Латвии двоих фигурантов уголовного дела, сообщает Госполиция.

Читать

Застрелил на охоте владельца охранной фирмы: бывший шеф полиции генерал Шулте получил реальный срок

Рижский окружной суд в Юрмале сегодня приговорил бывшего начальника Рижского регионального управления Государственной полиции генерала Юриса Шулте к семи годам и шести месяцам лишения свободы за убийство человека во время охоты, сообщили агентству LETA в суде.

Рижский окружной суд в Юрмале сегодня приговорил бывшего начальника Рижского регионального управления Государственной полиции генерала Юриса Шулте к семи годам и шести месяцам лишения свободы за убийство человека во время охоты, сообщили агентству LETA в суде.

Читать

Создателей мультфильма «Поток» наградят Орденом Трёх звёзд

Команда анимационного фильма «Поток», завоевавшего престижные международные награды, была удостоена Ордена Трёх звезд. 

Команда анимационного фильма «Поток», завоевавшего престижные международные награды, была удостоена Ордена Трёх звезд. 

Читать