4446
правок
Сложность ядра: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 79: | Строка 79: | ||
'''Теорема 2. Проверка принадлежности к ядру для линейных производственных игр является <math>co-\mathcal{NP}</math>-полной.''' | '''Теорема 2. Проверка принадлежности к ядру для линейных производственных игр является <math>co-\mathcal{NP}</math>-полной.''' | ||
Задача нахождения минимального дерева Штейнера в сети является <math>\mathcal{NP}</math>-сложной, поэтому в игре на дереве Штейнера значение <math>\gamma(S)</math> каждой коалиции S не может быть получено за полиномиальное время. Из этого следует, что дополнительная задача проверки принадлежности к ядру для игр на дереве Штейнера может не | Задача нахождения минимального дерева Штейнера в сети является <math>\mathcal{NP}</math>-сложной, поэтому в игре на дереве Штейнера значение <math>\gamma(S)</math> каждой коалиции S не может быть получено за полиномиальное время. Из этого следует, что дополнительная задача проверки принадлежности к ядру для игр на дереве Штейнера может не принадлежать к <math>\mathcal{NP}</math>. | ||
| Строка 88: | Строка 88: | ||
Пусть даны игра на дереве Штейнера <math>\Gamma_s = (N, \gamma)</math>, заданная на сети <math>G = (V, E; \omega)</math>, и подмножество <math>S \subseteq N</math>. Тогда в подигре <math>(S, \gamma_s)</math> значение <math>\gamma(S') \; (S' \subseteq S)</math> является весом минимального дерева Штейнера G относительно подмножества <math>S\ \cup \{ v_0 \}</math>, где все вершины в N \ S рассматриваются как коммутаторы, но не потребители. Далее, в работе Фанга и др. [4] было показано, что проверка полной сбалансированности игры на дереве Штейнера также является <math>\mathcal{NP}</math>-сложной. Это первый пример NP-сложности задачи для условия полной сбалансированности. | Пусть даны игра на дереве Штейнера <math>\Gamma_s = (N, \gamma)</math>, заданная на сети <math>G = (V, E; \omega)</math>, и подмножество <math>S \subseteq N</math>. Тогда в подигре <math>(S, \gamma_s)</math> значение <math>\gamma(S') \; (S' \subseteq S)</math> является весом минимального дерева Штейнера G относительно подмножества <math>S\ \cup \{ v_0 \}</math>, где все вершины в N \ S рассматриваются как коммутаторы, но не потребители. Далее, в работе Фанга и др. [4] было показано, что проверка полной сбалансированности игры на дереве Штейнера также является <math>\mathcal{NP}</math>-сложной. Это первый пример <math>\mathcal{NP}</math>-сложности задачи для условия полной сбалансированности. | ||
