4511
правок
Сложность ядра: различия между версиями
Перейти к навигации
Перейти к поиску
→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 96: | Строка 96: | ||
Результаты определения вычислительной сложности для ядер комбинаторно-оптимизационных игр были столь же разнообразны, как и для соответствующих задач комбинаторной оптимизации. Примеры: | Результаты определения вычислительной сложности для ядер комбинаторно-оптимизационных игр были столь же разнообразны, как и для соответствующих задач комбинаторной оптимизации. Примеры: | ||
(1) В играх на соответствие [ ] проверка сбалансированности, проверка принадлежности и нахождение члена ядра могут быть выполнены за полиномиальное время. | (1) В играх на соответствие [1] проверка сбалансированности, проверка принадлежности и нахождение члена ядра могут быть выполнены за полиномиальное время. | ||
(2) В играх о поведении потока и играх на остовном дереве с минимальной стоимостью [3, 4], в которых ядра всегда непустые, а член ядра может быть найден за полиномиальное время, задача проверки принадлежности является co-NP-полной. | (2) В играх о поведении потока и играх на остовном дереве с минимальной стоимостью [3, 4], в которых ядра всегда непустые, а член ядра может быть найден за полиномиальное время, задача проверки принадлежности является <math>co-\mathcal{NP}</math>-полной. | ||
(3) В играх с размещением объектов [ ] задача проверки сбалансированности в общем случае является NP-сложной, однако, учитывая информацию о непустоте ядра, можно эффективно выполнить как поиск члена ядра, так и проверку принадлежности. | (3) В играх с размещением объектов [5] задача проверки сбалансированности в общем случае является <math>\mathcal{NP}</math>-сложной, однако, учитывая информацию о непустоте ядра, можно эффективно выполнить как поиск члена ядра, так и проверку принадлежности. | ||
(4) В игре с суммой весов ребер, определенной на графе [2], все задачи проверки сбалансированности, проверки принадлежности и нахождения члена ядра являются NP-сложными. | (4) В игре с суммой весов ребер, определенной на графе [2], все задачи проверки сбалансированности, проверки принадлежности и нахождения члена ядра являются <math>\mathcal{NP}</math>-сложными. | ||
| Строка 108: | Строка 108: | ||
Когда ядро игры пусто, это стимулирует условия, обеспечивающие непустоту приближенных ядер. Естественным способом аппроксимации ядра является наименьшее ядро. Пусть (N, v) – кооперативная игра с прибылью. Пусть дано действительное число | Когда ядро игры пусто, это стимулирует условия, обеспечивающие непустоту приближенных ядер. Естественным способом аппроксимации ядра является ''наименьшее ядро''. Пусть (N, '''v''') – кооперативная игра с прибылью. Пусть дано действительное число <math>\varepsilon</math>. Определим <math>\varepsilon</math>-ядро, содержащее такие распределения, что <math>\mathbf{x}(S) \ge \mathbf{v}(S) - \varepsilon</math> для каждого непустого собственного подмножества S из N. ''Наименьшее ядро'' является пересечением всех непустых <math>\varepsilon</math>-ядер. Пусть <math>\varepsilon^*</math> - минимальное значение <math>\varepsilon</math>, такое, что <math>\varepsilon</math>-ядро пусто. Тогда наименьшее ядро совпадает с <math>\varepsilon^*</math>-ядром. | ||