Понятие NP-трудной и NP-полной задачи — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 1 промежуточная версия 1 участника)
(нет различий)

Текущая версия на 19:04, 4 сентября 2022

Определение класса NP-трудных задач

Язык [math]L[/math] называется NP-трудным (NPH), если для любого языка [math]L_{1}[/math], принадлежащего NP, [math]L_{1}[/math] сводится по Карпу к [math]L[/math] ([math]L_{1}\le L[/math]).

Определение класса NP-полных задач

Язык [math]L[/math] называется NP-полным (NPC), если он является NP-трудным и принадлежит классу NP.