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

'''Теорема 1. Пусть имеются игра о поведении потока <math>\Gamma_f = (E, \mathbf{v})</math>, заданная на сети <math>D = (V, E; \omega; s, t</math>) и вектор <math>\mathbf{x} : E \to R^+</math>, <math>\mathbf{x}(E) = \mathbf{v}(E)</math>. Задача о существовании коалиции <math>S \subset N</math>, такой, что <math>\mathbf{x}(S) < \mathbf{v}(S)</math>, является <math>\mathcal{NP}</math>-полной. Другими словами, проверка принадлежности к ядру для игр о поведении потока является <math>co-\mathcal{NP}</math>-полной.'''

Доказательство теоремы 1 позволяет прийти точно к такому же выводу для линейных производственных игр. В линейной производственной игре Оуэна [10] каждый игрок j <math>(j \in N)</math> является владельцем индивидуального вектора ресурсов <math>b^j</math>. Для коалиции S игроков прибыль, получаемая коалицией, является оптимальным значением следующей линейной программы:

<math>max \{ c^t y : Ay \le \sum_{j \in S} b^j, y \ge 0 \}.</math>