На днях Норберт Блюм опубликовал на архиве препринт с названием «A Solution of the P versus NP Problem». Таким образом Блюм претендует на решение одной из задач тысячелетия, за которую кроме почестей полагается 1 миллион долларов. В данной статье я собрал небольшое резюме об этом.
Читать полностью »
Рубрика «p vs np problem»
Новая заявка на решение задачи P vs. NP
2017-08-18 в 8:10, admin, рубрики: complexity, p vs np problem, Алгоритмы, Блог компании СПБАУ, математика, теория, теория сложности, теория сложности вычисленийПолиномиальный алгоритм для комбинаторной задачи (P=NP?)
2016-07-03 в 10:47, admin, рубрики: p vs np problem, p=np, Алгоритмы, криптография, математика, открытая математическая проблема, полиномиальный алгоритм, проблема перебора, метки: p vs np problem, p=np, открытая математическая проблема, полиномиальный алгоритм, проблема перебораВ этой статье я хотел бы рассказать о моем исследовании на тему равенства классов P и NP. Оригинал статьи вы можете прочитать здесь.
Небольшое введение.
Вообще проблема равенства классов — одна из самых главных открытых математических проблем. Ведь при положительном ответе, программисты смогут гораздо оптимизировать многие аспекты программы, а так же деятели науки смогут например расшифровывать геном за короткое время. Однако, многие ученые склоняются к отрицательному ответу. Мне же, как программисту, не мыслим отрицательный ответ, да и если посмотреть, мы уже придумали алгоритмы, сокращающие время перебора во много раз, чем путем полного перебора.
В моей статье написано все достаточно замудрено и сложно для понимания, здесь я бы хотел рассказать по-простому об этом исследовании, а так же дополнить статью новыми интересными открытиями, а так же поделиться с вами этим полиномиальным алгоритмом, для быстрого вычисления комбинаторных задач такого рода.
Читать полностью »