Задача разрешения называется NP-полной, если она сама принадлежит классу NP, а с другой стороны, произвольная задача из этого класса сводится к ней полиномиально (по Карпу). Класс таких задач обозначается NPC.
Диаграмма
Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.
