NP-полнота

• Определение NP-полноты

  • NP-полные задачи — это задачи, которые не могут быть решены за полиномиальное время, но могут быть проверены за полиномиальное время. 
  • NP-полнота является свойством класса задач, а не отдельной задачей. 

• Примеры NP-полных задач

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

• Методы решения NP-полных задач

  • Аппроксимация: поиск приближенного решения, отличающегося от оптимального не более чем в два раза. 
  • Рандомизация: использование случайности для увеличения среднего времени выполнения и снижения вероятности сбоя алгоритма. 
  • Ограничение структуры входных данных: использование специальных методов для решения задач на определенных типах графов. 
  • Параметризация: использование фиксированных параметров для ускорения алгоритмов. 
  • Эвристический подход: использование алгоритмов, которые работают «достаточно хорошо» без доказательства их эффективности. 

• Полнота при различных типах сокращений

  • Сокращение по Тьюрингу: возможность свести задачу к другой задаче за полиномиальное время с помощью подпрограммы. 
  • Логарифмическое сокращение: возможность сокращения задачи во много раз с использованием логарифмического объема пространства. 
  • Другие типы сокращений: существуют различные типы сокращений, которые могут быть использованы для определения NP-полноты. 

• Присвоение имен NP-полным задачам

  • Название «NP-complete» популяризировано Ахо, Хопкрофтом и Ульманом. 
  • Были предложены различные альтернативные названия, включая «Геркулесовый» и «ДОМАШНЕЕ животное». 

• Распространенные заблуждения

  • Заблуждения включают утверждение о сложности всех NP-полных задач, сложности некоторых задач при большом количестве решений и возможности экспоненциального времени решения. 
  • Некоторые задачи могут быть решены за субэкспоненциальное время, а некоторые случаи NP-полных задач могут быть легко решены. 

• Свойства NP-полноты

  • Множество NPC всех NP-полных задач не является замкнутым под операциями объединения, пересечения и сцепления. 
  • Неизвестно, является ли NPC замкнутым при дополнении, так как это зависит от NP=co-NP. 

• Рекомендации и дальнейшее чтение

  • Ссылки на классические книги и статьи, которые углубляют теорию NP-полноты и обсуждают практические аспекты.