Понятие NP-трудной и NP-полной задачи — различия между версиями
(→Определение класса NP-полных задач) |
(→Определение класса NP-трудных задач) |
||
| Строка 1: | Строка 1: | ||
==Понятие <tex>NP</tex>-трудной и <tex>NP</tex>-полной задачи== | ==Понятие <tex>NP</tex>-трудной и <tex>NP</tex>-полной задачи== | ||
==Определение класса <tex>NP</tex>-трудных задач== | ==Определение класса <tex>NP</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>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:50, 16 марта 2010
Понятие -трудной и -полной задачи
Определение класса -трудных задач
Язык называется -трудным (), если для любого языка принадлежащего , сводится по Карпу к ().
Определение класса -полных задач
Язык L называется -полным (), если он является -трудным и принадлежит классу .
