4446
правок
Сложность ядра: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 71: | Строка 71: | ||
Доказательство теоремы 1 позволяет прийти точно к такому же выводу для линейных производственных игр. В линейной производственной игре Оуэна [10] каждый игрок j <math>(j \in N)</math> является владельцем индивидуального вектора ресурсов <math>b^j</math>. Для коалиции S игроков прибыль, получаемая коалицией, является оптимальным значением следующей линейной программы: | Доказательство теоремы 1 позволяет прийти точно к такому же выводу для линейных производственных игр. В линейной производственной игре Оуэна [10] каждый игрок j <math>(j \in N)</math> является владельцем индивидуального вектора ресурсов <math>b^j</math>. Для коалиции S игроков прибыль, получаемая коалицией, является оптимальным значением следующей линейной программы: | ||
max | <math>max \{ c^t y : Ay \le \sum_{j \in S} b^j, y \ge 0 \}.</math> | ||
| Строка 77: | Строка 77: | ||
Теорема 2. Проверка принадлежности к ядру для линейных производственных игр является co-NP-полной. | '''Теорема 2. Проверка принадлежности к ядру для линейных производственных игр является <math>co-\mathcal{NP}</math>-полной.''' | ||
Задача нахождения минимального дерева Штейнера в сети является NP-сложной, поэтому в игре на дереве Штейнера значение | Задача нахождения минимального дерева Штейнера в сети является <math>\mathcal{NP}</math>-сложной, поэтому в игре на дереве Штейнера значение <math>\gamma(S)</math> каждой коалиции S не может быть получено за полиномиальное время. Из этого следует, что дополнительная задача проверки принадлежности к ядру для игр на дереве Штейнера не может быть <math>\mathcal{NP}</math>-сложной. | ||
Теорема 3. Пусть имеются игра на дереве Штейнера Fs = (N,y), заданная на сети G = (V; E;!), и вектор x N R+ с x(N) = y(N). Задача о существовании коалиции S С N, такой, что x(S) > y(S), является NP-сложной. Другими словами, проверка принадлежности к ядру для игр на дереве Штейнера является NP-сложной. | Теорема 3. Пусть имеются игра на дереве Штейнера Fs = (N,y), заданная на сети G = (V; E;!), и вектор x N R+ с x(N) = y(N). Задача о существовании коалиции S С N, такой, что x(S) > y(S), является <math>\mathcal{NP}</math>-сложной. Другими словами, проверка принадлежности к ядру для игр на дереве Штейнера является <math>\mathcal{NP}</math>-сложной. | ||
Теорема 4. Проверка сбалансированности для игр на дереве Штейнера является NP-сложной. | '''Теорема 4. Проверка сбалансированности для игр на дереве Штейнера является <math>\mathcal{NP}</math>-сложной.''' | ||
Пусть даны игра с деревом Штейнера Fs = (N,y), заданная на сети G = (V; E; !), и подмножество S С N. Тогда в подигре (S, ys) значение y(S') (S0 С S) является весом минимального дерева Штейнера G относительно подмножества S0 [ fv0g, где все вершины в N n S рассматриваются как коммутаторы, но не потребители. Далее, в работе Фанга и др. [ ] было показано, что проверка полной сбалансированности игры на дереве Штейнера также является NP-сложной. Это первый пример NP-сложности задачи для условия полной сбалансированности. | Пусть даны игра с деревом Штейнера Fs = (N,y), заданная на сети G = (V; E; !), и подмножество S С N. Тогда в подигре (S, ys) значение y(S') (S0 С S) является весом минимального дерева Штейнера G относительно подмножества S0 [ fv0g, где все вершины в N n S рассматриваются как коммутаторы, но не потребители. Далее, в работе Фанга и др. [ ] было показано, что проверка полной сбалансированности игры на дереве Штейнера также является <math>\mathcal{NP}</math>-сложной. Это первый пример NP-сложности задачи для условия полной сбалансированности. | ||
Теорема 5. Проверка полной сбалансированности для игр на дереве Штейнера является NP-сложной. | '''Теорема 5. Проверка полной сбалансированности для игр на дереве Штейнера является <math>\mathcal{NP}</math>-сложной.''' | ||
== Применение == | == Применение == | ||
