Алгоритмы на языке «разделяй и властвуй». Понятие о классах r и np, np-полных задачах

Силовой аспект проблемы NP-полноты
Проблема является строго NP-полной, если она имеет частичные проблемы.называется делом, где: Если числовых параметров задачи не существует (т. е. максимальное значение величин, встречающихся в этой задаче, ограничено сверху длиной полинома).
Если числовых параметров задачи не существует (т. е. максимальное значение величин, встречающихся в этой задаче, ограничено сверху длиной многочлена).
Проблема NP-полноты.
Такой класс задач называется NPCS. Если гипотеза P ≠ NP верна, то для задачи NPCS не существует псевдополиномиального алгоритма.Примеры задач NP-полноты
К вопросу о реализации формул Буля
«Пятна» — это кратчайшие решения размерности n ×
Вопрос коммивояжера
проблема Штейнера
Проблема раскраски графа
Проблема с покрытием соха (поверхность)
Вопрос об охвате коллекции
Вопрос выбора
Проблема независимости множества
Сапер (игра)
тетрис

Литературы

1. 
   
   Гэри М., Джонсон Д.Вычислительныемашины и труднорешаемые задачи. М.: Мир, 1982.
   
2. 
   
   Томас Х. Кормен и др.Боб. 34 НП-полнота // Алгоритмы: построение и анализ = Введение в алгоритмы. — 2-е изд. — М.: «Вильямс», 2006. — 1296 с. - ISBN 0-07-013151-1.
   
3. 
   
   Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман.Введение в теорию автоматов, языки и вычисления. — М.: «Вильямс», 2002. — 528 с. - ISBN 0-201-44124-1.
   
4. 
   Сайты:
   

   1. https://en.wikipedia.org/wiki/P_versus_NP_problem

      
      

   2. http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2025%20-%20P%20and%20NP.htm

      
      
   3. 
      
      https://uz.wikipedia.org/