Изменения
→Определение класса NP-трудных задач
==Определение класса <tex>NP</tex>-трудных задач== Язык <tex>L</tex> называется <tex>'''NP</tex>'''-трудным (<tex>'''NPH</tex>'''), если для любого языка <tex>L_{1}</tex>, принадлежащего <tex>'''NP</tex>''', <tex>L_{1}</tex> сводится по Карпу к <tex>L</tex> (<tex>L_{1}\le L</tex>).
==Определение класса <tex>NP</tex>-полных задач==
Язык L называется <tex>NP</tex>-полным (<tex>NPC</tex>), если он является <tex>NP</tex>-трудным и принадлежит классу <tex>NP</tex>.
