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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Определение класса NP-трудных задач)
Строка 2: Строка 2:
 
Язык <tex>L</tex> называется '''NP'''-трудным ('''NPH'''), если для любого языка <tex>L_{1}</tex>, принадлежащего '''NP''', <tex>L_{1}</tex> сводится по Карпу к <tex>L</tex> (<tex>L_{1}\le L</tex>).
 
Язык <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>-полных задач==
+
==Определение класса NP-полных задач==
−
Язык L называется <tex>NP</tex>-полным (<tex>NPC</tex>), если он является <tex>NP</tex>-трудным и принадлежит классу <tex>NP</tex>.
+
Язык <tex>L</tex> называется '''NP'''-полным ('''NPC'''), если он является '''NP'''-трудным и принадлежит классу '''NP'''.

Версия 09:38, 3 мая 2010

Определение класса 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.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Понятие_NP-трудной_и_NP-полной_задачи&oldid=962»