В пену

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

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

Новости, Наука | RRB 12:34 20.11.2015

17 комментариев | 97 за, 0 против |

Tegucigalpa »

#1 | 12:36 20.11.2015 | Кому: Всем

Теперь маленьких математиков будут пугать по-настоящему.

portus »

#2 | 12:39 20.11.2015 | Кому: Всем

Я сперва подумал, что это тот Бабай, что с шумом ездил воевать и сдриснул с войны когда стало страшно! :0) Ничосе, думаю, мыслитель!

Skaalex »

#3 | 12:39 20.11.2015 | Кому: Всем

Был у нас тут один граф, так его выпиздили не сравнивая

Antic »

#4 | 12:52 20.11.2015 | Кому: Skaalex

> Был у нас тут один граф, так его выпиздили не сравнивая

Он был несравненный!!!

gurgutan »

#5 | 13:10 20.11.2015 | Кому: Skaalex

Гомоморфный, чтоль, был?

Beer_admin »

#6 | 13:10 20.11.2015 | Кому: Skaalex

> Был у нас тут один граф, так его выпиздили не сравнивая

Это у которого на вершине Пирамиды Маслоу было то самое созвучное финское, из-за чего категорически безвинно и пострадал?

Beefeater »

#7 | 13:11 20.11.2015 | Кому: gurgutan

> Гомоморфный столь был?

Кому Граф де Незомбо может быть гомеоморфен? Разве что остовному графу множества всех множеств!

porcupine_free »

#8 | 13:12 20.11.2015 | Кому: portus

> и сдриснул с войны когда стало страшно!

Я что-то этот момент пропустил. А где про это почитать/посмотреть?

Uksare »

#9 | 13:18 20.11.2015 | Кому: Всем

Интересно, сколько набралось бы плюсов, если бы математика звали Джон Смит?

Skaalex »

#10 | 13:19 20.11.2015 | Кому: Beer_admin

> Это у которого на вершине Пирамиды Маслоу было то самое созвучное финское, из-за чего категорически безвинно и пострадал?

Он самый

porcupine_free »

#11 | 13:20 20.11.2015 | Кому: Uksare

> Интересно, сколько набралось бы плюсов, если бы математика звали Джон Смит?

Столько же. Бабай же разработал теоретический алгоритм, позволяющий существенно ускорить сравнение графов друг с другом! Заживём теперь!

gurgutan »

#12 | 13:25 20.11.2015 | Кому: Всем

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

pks_ru
шутник »

#13 | 13:35 20.11.2015 | Кому: gurgutan

> становятся похожи на вечный двигатель, с тем лишь отличием, что математики допускают их существование.

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

stormlord »

#14 | 14:31 20.11.2015 | Кому: Всем

Я ничего не понял, но это, наверное, круто.

bas150 »

#15 | 15:25 20.11.2015 | Кому: Всем

На проблеме изоморфизма графов и на основе метода доказательства с нулевым разглашением строятся некоторые криптографические алгоритмы для аутентификации. Если окажется, что изоморфизм графов вычислительно на самом деле не очень сложная задача, а до сих пор верили в обратное, то некоторые алгоритмы из криптографии исчезнут.

BooldozErrr »

#16 | 15:34 20.11.2015 | Кому: stormlord

> Я ничего не понял, но это, наверное, круто.

Я тоже не особо понял, но вроде как Бабай почти придумал, как Калиостро с Монте-Кристо сравнивать.

Кирилл Борисенко »

#17 | 20:53 20.11.2015 | Кому: stormlord

> Я ничего не понял, но это, наверное, круто.

На человеческий язык это переводится как программа, реализующая алгоритм "я тут прикинул и получил точный ответ".
Не "произвёл расчёты и получил точный ответ", а именно "прикинул и получил точный ответ".

Войдите или зарегистрируйтесь чтобы писать комментарии.

Логин
Пароль
	Запомнить