РусУкр
11.12.2017 г.
Промышленный комитет Рады готовит введение перспективного плана госзакупок на 3-5 лет для долгосрочных инфраструктурных проектов
"Дети одновременно не рождаются": при рождении двойняшек новое пособие в РФ дадут только на первого ребенка
Назван лучший фильм ужасов 2017 года
"Странная награда": Путин вручил премию правозащитнице Людмиле Алексеевой
Исследователи доказали существование новой формы материи
КНДР готова к созданию современного биологического оружия
Программисты создали необнаруживаемый вирус для ОС Windows
Порошенко показал видео испытаний нового сверхмощного БТР
Американская военная техника в Польше упала в канаву (ВИДЕО)
Новости мира: Нетаньяху обратился к палестинцам
"Гордого презрения" не получилось: Россия просит МОК пересмотреть решение об участии в Олимпиаде
Стала известна причина «тормозов» старых iPhone
Путин прилетел на авиабазу в Хмеймим и приказал вывести российские войска из Сирии
В США аналитики спрогнозировали результаты войны с Россией и Китаем
"Стальная платина в штанах": в Сети высмеяли "боягуза" Пескова
Учеными названа неожиданная опасность недосыпания
Беглый бизнесмен Курченко подал в суд на Порошенко
Руслана Лыжичко: На сцену с открытой раной
Будущее Украины - ключ к успеху Польши, - Портников
Синоптики предупреждают об ухудшении погодных условий
Депутаты Госдумы получили указание отказаться от поездок в Европу
Мерзавцы доводят до катастрофы все, к чему прикасаются, - Мирослав Гай
Курс биткоина 11 декабря после обвала в субботу начинает восстанавливать позиции
«Россети» боятся идти в Крым из-за санкций
Боевики "ДНР" заблокировали поселок под Донецком
На черном рынке курс доллара стремительно растет
СМИ назвали попадающие под новые санкции США российские предприятия
Известная российская актриса пополнила базу "Миротворца"
Bloomberg: Русские хакеры похитили около $10 млн в США и РФ
Саакашвили доставили в Печерский суд (ФОТО)
Уникальный пятизвездочный отель, который строят в бывшем карьере (ФОТО+ВИДЕО)
Кремль поручил превратить выборы президента в праздник
Украина соскочила с газовой иглы России, но осталась проблема, - Пономарев (ВИДЕО)
Дудл Google в честь Макса Борна
Сутки на фронте: боевики активизировались на Луганском направлении, есть раненые, - штаб АТО
Рынок земли: Утренние новости от Олега Пономаря
В Калифорнии бушует пожар
Признаки шизофрении: В Луганске думают, что вернутся в Украину, а Плотницкого объявили шпионом Киева, - Олена Степова
София Ротару - "Престарелая пособница АТО"
В Украине самые низкие зарплаты в Европе (ИНФОГРАФИКА)
"Голос. Діти-4": кто прошел в суперфинал
Известный производитель детского питания отзывает партию из-за возможного заражение сальмонеллой
На центральную Европу в воскресенье обрушились сильные снегопады
Изменение цен на АЗС за выходные: Средняя стоимость топлива на 11 декабря
"Киевавтодор" увеличил количество спецтехники
США приготовились к мощному удару по России
Должность премьер-министра в Польше уже не имеет "сакрального" смысла, - Портников
Россияне, учите лучше китайский, забудьте про Украину! - Кирилл Сазонов
Климкин: Кто-то настойчиво пытается рассорить нас с Польшей и сорвать визит Анджея Дуды в Украину
МИД Польши об "антипольском событии на территории Украины"
Кремль и Путин для многих из нашей политической элиты ближе, чем Брюссели и Вашингтоны, - политолог
РФ готовится к войне: сотни российских танков и пушек появятся в Беларуси
Сколько украинцы будут отдыхать на рождественско-новогодние праздники
Пусть покидают эту страну или учат язык: Фарион предлагает исключить русский язык из употребления, особенно во время войны
"Наша задача – сделать настоящую революцию": Сторонники Саакашвили избрали нового лидера
Страна мечты: Политический флешмоб Святослава Вакарчука (ВИДЕО)

10.12.2017 г.
Путин уйдет не в результате революции, его свергнут люди, по которым ударят новые западные санкции, - Пионтковский
Первый в Украине электробус "Электрон" - экологический транспорт нового поколения, - Порошенко (ВИДЕО)
Как изменились настроения крымчан после аннексии полуострова (ИНФОГРАФИКА)
Папа Римский предложил изменить молитву «Отче наш»
Все новости »

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

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

 

 

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

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

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

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

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

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

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

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

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


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

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




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

Комплексы Patriot оказались бесполезны против ракет советского времени (5303)

«Гром-2»: в Украине разрабатывают новый комплекс оперативно-тактического назначения (5285)

Новости технологий: Илон Маск спровоцировал всемирный дефицит батареек (4081)

В Китае создали плащ-невидимку (ВИДЕО) (2632)

Ученые нашли белый НЛО (2498)

Стало известно, когда программисты останутся без работы (1819)

Ждем с нетерпением: ОТРК “Гром” в следующем году идёт “на полигон”, - Злой одессит (1714)

В Германии запустили новый скоростной поезд (ВИДЕО) (1666)

Космос: В Австралии сфотографировали полет НЛО (ФОТО) (1643)

США спустили на воду эсминец будущего (ВИДЕО) (1639)

Владельцы iPhone столкнулись с новой проблемой (1610)

Ученые нашли признак скорой смерти (1595)

Истребитель F-35 начал разваливаться в полете (1542)

Нейробиологи раскрыли простой способ улучшения памяти (1447)

США прекратят разработку рельсотрона (1400)

Рейтинг новостей

Как изменились настроения крымчан после аннексии полуострова (ИНФОГРАФИКА) (19136)

Сколько украинцы будут отдыхать на рождественско-новогодние праздники (8444)

"І на оновленій землі Врага не буде, супостата": Диалог Тарапуньки и Штепселя в 1967 году о том, что будет в 2017-м (ВИДЕО) (4688)

Страна мечты: Политический флешмоб Святослава Вакарчука (ВИДЕО) (3089)

Новости Украины: Порошенко назвал главную национальную ценность каждого украинца (3023)

Первый в Украине электробус "Электрон" - экологический транспорт нового поколения, - Порошенко (ВИДЕО) (2715)

София Ротару - "Престарелая пособница АТО" (2501)

Известная российская актриса пополнила базу "Миротворца" (2426)

Под Львовом на парковке подорвали автобус с польскими номерами (2321)

"Наша задача – сделать настоящую революцию": Сторонники Саакашвили избрали нового лидера (2245)

Сторонники Михаила Саакашвили разбили магазин Roshen (2243)

Путин уйдет не в результате революции, его свергнут люди, по которым ударят новые западные санкции, - Пионтковский (2120)

Украина соскочила с газовой иглы России, но осталась проблема, - Пономарев (ВИДЕО) (2117)

В Донецкой области нашли тайник с оружием из РФ (ВИДЕО) (2100)

Як змінилися настрої кримчан після анексії півострова (ІНФОГРАФІКА) (2059)



Последние новости «I» в соцсетях

  

Новости партнеров

Загрузка...
Загрузка...
bigmir)net TOP 100

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

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

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

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

Статус

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