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