Понятие NP-трудной и NP-полной задачи

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

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

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

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