Понятие NP-трудной и NP-полной задачи
(перенаправлено с «NP-полнота»)
Определение класса NP-трудных задач
Язык
называется NP-трудным (NPH), если для любого языка , принадлежащего NP, сводится по Карпу к ( ).Определение класса NP-полных задач
Язык
называется NP-полным (NPC), если он является NP-трудным и принадлежит классу NP.