Сложность ядра: различия между версиями

(2) В играх о поведении потока и играх на остовном дереве с минимальной стоимостью [3, 4], в которых ядра всегда непустые, а член ядра может быть найден за полиномиальное время, задача проверки принадлежности является <math>co-\mathcal{NP}</math>-полной.

(3) В играх с размещением объектов [5] задача проверки сбалансированности в общем случае является <math>\mathcal{NP}</math>-сложной, однако, учитывая информацию о непустоте ядра, можно эффективно выполнить как поиск члена ядра, так и проверку принадлежности.

Чтобы изучение сложности и алгоритмов для кооперативных игр для соответствующих областей применения имело смысл, предлагается рассматривать вычислительную сложность как важный фактор при оценке рациональности и справедливости концепции решения, что вытекает из понятия ограниченной рациональности [3, 8]. Иными словами, игроки не готовы тратить на поиск наиболее подходящего решения больше полиномиального времени. В случае, когда решений игры не существует или их трудно вычислить либо проверить, может оказаться не просто отбросить задачу как безнадежную, особенно когда игра возникает в важных областях применения. Поэтому для решения задачи предлагаются различные концептуальные подходы.