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

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

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

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

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

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

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

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

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

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

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

Задержано руководство самоуправления Екабпилса: в том числе мэр города Райвис Рагайнис

По поручению Европейской прокуратуры (EPPO) Бюро по предотвращению и борьбе с коррупцией (KNAB) в четверг провело обыски и задержало пять человек, в том числе мэра Екабпилсского края Райвиса Рагайниса (LZP), других государственных должностных лиц и представителей частных компаний в рамках расследования строительства дамбы против наводнений, финансируемой Евросоюзом, стоимостью 16,9 миллиона евро. Об этом говорится в пресс-релизе EPPO.

По поручению Европейской прокуратуры (EPPO) Бюро по предотвращению и борьбе с коррупцией (KNAB) в четверг провело обыски и задержало пять человек, в том числе мэра Екабпилсского края Райвиса Рагайниса (LZP), других государственных должностных лиц и представителей частных компаний в рамках расследования строительства дамбы против наводнений, финансируемой Евросоюзом, стоимостью 16,9 миллиона евро. Об этом говорится в пресс-релизе EPPO.

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

Латвии адресовано 18 «языковых» рекомендаций: Алексей Димитров — о документе ЕС

-2 апреля Комитет министров Совета Европы (представители государств) принял резолюцию о соблюдении Латвией Рамочной конвенции о защите национальных меньшинств. Принятие резолюции заняло довольно много времени - с момента принятия экспертного доклада прошло почти полтора года, - написал Алексей Димитров, юрист-международник, на своей страничке в Фейсбуке.

-2 апреля Комитет министров Совета Европы (представители государств) принял резолюцию о соблюдении Латвией Рамочной конвенции о защите национальных меньшинств. Принятие резолюции заняло довольно много времени - с момента принятия экспертного доклада прошло почти полтора года, - написал Алексей Димитров, юрист-международник, на своей страничке в Фейсбуке.

Читать

Политолог называет тарифы Трампа краткосрочным шоком

Новые таможенные пошлины, объявленные президентом США Дональдом Трампом, скорее всего, являются краткосрочным шоком, считает профессор кафедры политологии Латвийского университета Жанета Озолиня.

Новые таможенные пошлины, объявленные президентом США Дональдом Трампом, скорее всего, являются краткосрочным шоком, считает профессор кафедры политологии Латвийского университета Жанета Озолиня.

Читать

У латвийского флага есть альтернативные версии? Людей возмутил красно-бело-красный символ

Многие жители Риги удивились появившимся на некоторых учреждениях города флагам. Флаги были красно-бело-красными, но белая часть шире красных двух. Что это такое? У латвийского флага есть альтернативные версии? 

Многие жители Риги удивились появившимся на некоторых учреждениях города флагам. Флаги были красно-бело-красными, но белая часть шире красных двух. Что это такое? У латвийского флага есть альтернативные версии? 

Читать

Дюжина людей поёт песни протеста у здания Сейма: за права трансгендеров в Латвии

Утром в четверг перед зданием Сейма проходит песенная акция протеста, в которой несколько десятков человек выступают за права трансгендеров в Латвии.

Утром в четверг перед зданием Сейма проходит песенная акция протеста, в которой несколько десятков человек выступают за права трансгендеров в Латвии.

Читать

Дональд Трамп ввёл пошлины против 183 стран и ЕС: до 49 процентов! (СПИСОК)

Таможенные пошлины, о которых Дональд Трамп объявил в среду, стали самыми масштабными торговыми ограничениями со стороны США за последнее столетие. Сам Трамп назвал этот день "Днём освобождения"
В Розовом саду Белого дома в среду президент Дональд Трамп озвучил, какими именно налогами на импорт он обложил разные страны и товары. Это мероприятие он сам назвал "День экономической независимости Америки".

Таможенные пошлины, о которых Дональд Трамп объявил в среду, стали самыми масштабными торговыми ограничениями со стороны США за последнее столетие. Сам Трамп назвал этот день "Днём освобождения"
В Розовом саду Белого дома в среду президент Дональд Трамп озвучил, какими именно налогами на импорт он обложил разные страны и товары. Это мероприятие он сам назвал "День экономической независимости Америки".

Читать

Из Даугавы достали труп: он провел в воде длительное время

В центре Риги, на набережной Даугавы, днем в среду, 2 апреля, очевидцы заметили в воде человеческую фигуру и вызвали спасателей. При проверке информации подозрения подтвердились - в воде был замечен утопленник, сообщает программа Degpunktā телеканала TV3.

В центре Риги, на набережной Даугавы, днем в среду, 2 апреля, очевидцы заметили в воде человеческую фигуру и вызвали спасателей. При проверке информации подозрения подтвердились - в воде был замечен утопленник, сообщает программа Degpunktā телеканала TV3.

Читать