Рубрика «p=np»

в 8:01, , рубрики: crypto, np, np-complete, np-hard, NP-полная задача, p=np, PSPACE, timeweb_статьи, Алгоритмы, Блог компании Timeweb Cloud, задача тысячелетия, информационная безопасность, класс NP, классы сложности, криптография, математика, машина Тьюринга, теоретическая информатика, теория алгоритмов, теория вычислимости

Есть проблемы гораздо сложнее, чем NP-Complete - 1

Люди часто сравнивают P и NP в таком духе, что проблемы P простые, а NP — сложные. Но это чрезмерное упрощение. На самом деле проблемы могут быть намного, намного сложнее, чем NP.

В этом смысле можно вспомнить интеллектуально-фантастический триллер Travelling Salesman (Коммивояжёр, 2012) о четырёх математиках, нанятых правительством США для решения самой сложной проблемы в истории информатики — равенства классов сложности P и NP (P versus NP problem). И им это удалось. Чиновник министерства обороны США предлагает за их алгоритм вознаграждение $10 млн. Но сами математики слишком хорошо понимают, какие разрушительные последствия принесёт в мир их открытие. Один из лучших фильмов про математику в истории кинематографа…
Читать полностью »

в 13:27, , рубрики: p=np, Алгоритмы, задача коммивояжёра, кристофидес, математика, Научно-популярное, метки:

Спустя десятилетия застоя, найдены новые короткие пути для задачи коммивояжёра

image

Не так давно команда исследователей из Стэнфорда и Университета Макгилла побили 35-летний рекорд по информатике на невообразимо малую величину – на четыре сотых триллионной триллионной триллионной доли процента. Прорыв – сделанный в классической для информатики задаче коммивояжёра – был слишком малым для какого бы то ни было практического значения, но он вдохнул новую жизнь в поиски улучшенных приближённых решений.

Задача формируется так: для набора городов, соединённых дорогами, необходимо найти кратчайший путь посещения каждого города с возвратом в точку старта. У решений задачи есть практические применения от сверления отверстий в печатных платах до управления расписанием задач на компьютере и упорядочивания свойств генома.
Читать полностью »

в 10:47, , рубрики: p vs np problem, p=np, Алгоритмы, криптография, математика, открытая математическая проблема, полиномиальный алгоритм, проблема перебора, метки: , , , ,

В этой статье я хотел бы рассказать о моем исследовании на тему равенства классов P и NP. Оригинал статьи вы можете прочитать здесь.

Небольшое введение.

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

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

в 14:12, , рубрики: p=np, Алгоритмы, биоинформатика

Гипотетически предположим, что вы сумели доказать равенство P=NP. Что же теперь нужно сделать для обретения господства над целым миром?
Читать полностью »

в 21:04, , рубрики: p=np, математика

Наткнулся на интересную статью, к сожалению не знаю, как вставить ссылку на внешний ресурс, поэтому оформляю как пост.

Ученый доказал равенство классов P и NP, за решение которого Математический институт Клэя назначил премию в миллион долларов США.

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

Читать полностью »

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js