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

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

Версия 00:49, 16 марта 2010

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

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

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