На днях Норберт Блюм опубликовал на архиве препринт с названием «A Solution of the P versus NP Problem». Таким образом Блюм претендует на решение одной из задач тысячелетия, за которую кроме почестей полагается 1 миллион долларов. В данной статье я собрал небольшое резюме об этом.
Читать полностью »
Рубрика «теория сложности вычислений»
Новая заявка на решение задачи P vs. NP
2017-08-18 в 8:10, admin, рубрики: complexity, p vs np problem, Алгоритмы, Блог компании СПБАУ, математика, теория, теория сложности, теория сложности вычисленийОпубликован быстрый алгоритм для задачи изоморфизма графов
2015-12-15 в 23:12, admin, рубрики: Занимательные задачки, изоморфизм графов, класс NP, класс P, математика, теоретическая информатика, теория сложности вычислений, метки: изоморфизм графов 
Эти два графа являются изоморфными
Математик Ласло Бабай (László Babai) с факультета компьютерных наук и математики Чикагского университета представил быстрый новый алгоритм для решения задачи изоморфизма графов — одной из фундаментальных проблем теории сложности вычислений. Алгоритм приводит проблему очень близко к классу P. По мнению некоторых специалистов, это один из самых значительных результатов в теоретической информатике за десятилетие, если не за несколько десятилетий.
Читать полностью »