РусУкр
27.05.2018 г.
Украине опасность несет само существование Московии, - Аnti-colorados
Конфликт Польши и Украины: В дело вмешается важный "игрок"
Дождались: В Украине изменится погода
Евгений Платон назвал главный кошмар Путина
"Хорошие воспоминания": Популярная голливудская звезда похвасталась фото из Украины
"Нам очень приятно победить в Украине": Эмоциональный Зидан восхитился украинцами
"Под Донецком назревает катастрофа": Георгий Тука забил тревогу
Бронегруппа украинских войск попала в засаду. Стало известно о трагических последствиях
«Диванная сотня» и орки: Бл@ди, сэр..., - Кирилл Сазонов
Сегодня украинцы будут наблюдать редкое космическое явление. Кому стоит опасаться?
Резонансные данные: В США сразу знали о причастности РФ к катастрофе МН17 на Донбассе
Несмотря на Троицу, оккупанты полтора часа из 120- и 82-мм минометов обстреливали Зайцево, - Минобороны
Госизмена, или Воронежу не расслабляться: Пацаны из Госдумы на "правильном пути", - Ганапольський
Дефолт не предлагать: Украина за три года может получить ВВП $4 тыс. на душу, - экономист (ИНФОГРАФИКА)
Военный лицей на Луганщине воспитал уже второй выпуск верных сыновей Украины
Украина предупредила НАТО о разработке Москвой химоружия для гибридной войны
В Европе хотят запретить одноразовую посуду из пластика
СБУ: На Луганщине под обстрелом погибли двое спецназовцев "Альфы"
Распыление газов в школах как часть гибридной войны: нас никто не защитит, кроме нас самих, - Мирослав Гай
Валютная либерализация — шанс, которым нужно правильно воспользоваться
Пусть сосет лапу: Министр социальной политики объяснил, почему Украина не выплачивает пенсию Януковичу
В ожидании наступления "Хунты": оккупанты в истерике, а украинцы пугают из своих окопов "Джавелинами" (ФОТО)
Путинские пропагандисты открыто высмеяли главаря Крыма в эфире росТВ: в сети иронизируют (ВИДЕО)
Киев спасен: Коммунальщики за ночь очистили от грязи фан-зоны и фонтан в парке Шевченко
Украинские инженеры разрабатывают боевую технику нового поколения (ФОТО)
Неравный брак: Обезвреживание "людей-ракет"- президентское дело , - Виталий Портников
Делегаты Литвы и Канады в ПА НАТО выступили против блокирования Венгрией сотрудничества Альянса с Украиной
НАТО и Газпром: Утренние новости от Олега Пономаря
На Донбассе разгромили пункт боевиков. Много убитых и раненых

25.05.2018 г.
Остановить или замедлить: Украине предложили интересный способ ударить по путинскому газопроводу
В Сиднее стартовал крупнейший фестиваль света
+ 60-70%: В НКРЭКУ рассказали о пересмотре цен на газ для украинцев
Сергей Шнуров разводится с женой Матильдой
Украинцев впечатлило видео удара по боевикам на Донбассе, снятое с высоты птичьего полета
Путин не сможет избежать наказания, - Слава Рабинович
Новости дня: Венгрия официально призвала пересмотреть политику НАТО в отношении Украины
"Они очень хотят этого. Но и мы тоже": американско-северокорейский саммит может состояться
Рис теряет свои полезные свойства из-за изменений климата, - ученые
Огромный астероид стал причиной резкого потепления на Земле, - ученые
Общество готово поверить в организацию встречи с Трампом за деньги, - Сергей Руденко
Певица Дуа Липа опубликовала фото со стадиона "Олимпийский"
Названа самая высокооплачиваемая модель мира (ФОТО)
УПЦ МП выступила против автокефалии для УПЦ КП и УАПЦ
Инвесторы кинулись в золото
Тысяча фанатов "Реала" сдали билеты на финальный матч ЛЧ, - УЕФА
Идут торги: Яценюк планирует зайти в Раду при помощи Гройсмана
Мустафа Найем: КС должен отменить назначение омбудсмена
Порошенко о достижениях «НИБУЛОНа»: экономика растет благодаря таким локомотивам, как Вадатурский
ЕС и НАТО призвали Россию признать ответственность за крушение MH17
В полиции Киева рассказали про нападавших на фанатов "Ливерпуля"
Иностранные инвесторы ускорили “слив” российских ценных бумаг, - Злой одессит
Чем живет фан-городок Лиги чемпионов на Крещатике
Названы новые способы для борьбы с курением
МВФ согласился на уступки по цене на газ для Украины, - источник
Мустафу Джемилева удостоили американской награды NED
Умная колонка сама записала разговор двух людей и отправила его постороннему человеку
Без дальнобойщиков и с виртуальным офисом: как технологии изменят жизнь
Айдер Муждабаев: Надо призвать страны бойкотировать чемпионат мира в террористической стране
В Нью-Йорке арестовали Вайнштейна
Курс украинской криптовалюты Karbo за неделю вырос на 43%
Все новости »

Математик из США достиг прогресса в решении «проблемы тысячелетия»

Новости технологий, 20.11.2015
 
Печать Отправить на почту

 

 

Математик Ласло Бабай из Чикагского университета в США разработал теоретический алгоритм, позволяющий существенно ускорить сравнение графов друг с другом.

Исследование ученого связано с проблемой равенства классов P и NP, являющейся одной из «проблем тысячелетия». Об этом сообщает Nature News, информирует news.enovosty.com.

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

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

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

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

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

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

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


По материалам Lenta.ru

В данный момент Вы читаете новость "Математик из США достиг прогресса в решении «проблемы тысячелетия»". Вас также, возможно, заинтересуют другие последние новости Украины и мира на enovosty.com



Аналитика





Новости технологий

Обычное окно может превратиться в солнечную панель и телевизор (2030)

Google отказалась от своего лозунга (1961)

Отправить модные Aple на пенсию: Американцы анонсировали выход революционного смартфона (ВИДЕО) (1829)

Новая охлаждающая краска для домов сможет заменить кондиционеры (1808)

Сделано в Украине: уникальные электробайки MyBro (1806)

iPhone: Apple будет комплектовать смартфоны дополнительным устройством (1715)

HTC выпустила новый флагманский смартфон (ФОТО) (1370)

Ученые назвали простое средство от преждевременной смерти (1320)

Появилась информация об интимных отношениях в космосе (1267)

Умная колонка сама записала разговор двух людей и отправила его постороннему человеку (1208)

В запястья американских солдат внедрят чипы (1164)

Блогер снял странное существо в заброшенном здании (ВИДЕО) (1087)

Космос: Блуждающая звезда доберется до Солнечной системы раньше, чем ожидалось (1062)

Огромный астероид стал причиной резкого потепления на Земле, - ученые (983)

Уголь теряет свои позиции в мире, - прогнозы аналитиков (954)

На Донбассе разгромили пункт боевиков. Много убитых и раненых (911)

НАТО и Газпром: Утренние новости от Олега Пономаря (625)

Украинские инженеры разрабатывают боевую технику нового поколения (ФОТО) (418)

Неравный брак: Обезвреживание "людей-ракет"- президентское дело , - Виталий Портников (332)

В ожидании наступления "Хунты": оккупанты в истерике, а украинцы пугают из своих окопов "Джавелинами" (ФОТО) (314)

Путинские пропагандисты открыто высмеяли главаря Крыма в эфире росТВ: в сети иронизируют (ВИДЕО) (283)

Киев спасен: Коммунальщики за ночь очистили от грязи фан-зоны и фонтан в парке Шевченко (148)

Делегаты Литвы и Канады в ПА НАТО выступили против блокирования Венгрией сотрудничества Альянса с Украиной (109)

Пусть сосет лапу: Министр социальной политики объяснил, почему Украина не выплачивает пенсию Януковичу (107)

Валютная либерализация — шанс, которым нужно правильно воспользоваться (37)

Распыление газов в школах как часть гибридной войны: нас никто не защитит, кроме нас самих, - Мирослав Гай (34)



Афиша 

Вся Афиша    >>


bigmir)net TOP 100

Экономические новости

Ежедневная деловая газета

Украинский бизнес портал

Электронный деловой журнал

Статус

Еженедельный деловой журнал