4551
правка
Сложность ядра: различия между версиями
Материал из WEGA
м
→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 98: | Строка 98: | ||
(1) В играх на соответствие [ ] проверка сбалансированности, проверка принадлежности и нахождение члена ядра могут быть выполнены за полиномиальное время. | (1) В играх на соответствие [ ] проверка сбалансированности, проверка принадлежности и нахождение члена ядра могут быть выполнены за полиномиальное время. | ||
(2) В играх о | (2) В играх о поведении потока и играх на остовном дереве с минимальной стоимостью [3, 4], в которых ядра всегда непустые, а член ядра может быть найден за полиномиальное время, задача проверки принадлежности является co-NP-полной. | ||
(3) В играх с размещением объектов [ ] задача проверки сбалансированности в общем случае является NP-сложной, однако, учитывая информацию о непустоте ядра, можно эффективно выполнить как поиск члена ядра, так и проверку принадлежности. | (3) В играх с размещением объектов [ ] задача проверки сбалансированности в общем случае является NP-сложной, однако, учитывая информацию о непустоте ядра, можно эффективно выполнить как поиск члена ядра, так и проверку принадлежности. | ||
