• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Граничные классы для задач о доминирующем множестве и раскраске и их приложения

2015

Уже почти полвека проблема «P≠NP» является одной из самых известных и знаменитых математических проблем, ее научное значение выходит далеко за рамки чистой математики. А именно, в содержательном смысле хотелось бы понять, почему одни задачи допускают простое алгоритмическое решение, а другие нет. Есть ли «простые» критерии полиномиальной разрешимости и как различать случаи «простых» и «трудных» подзадач одной и той же задачи. 

Публикации по проекту:


Malyshev D. A complexity dichotomy and a new boundary class for the dominating set problem // Journal of Combinatorial Optimization. 2016. Vol. 32. No. 1. P. 226-243. doi