Сложность ядра: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 66: | Строка 66: | ||
== Основные результаты == | == Основные результаты == | ||
'''Теорема 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. Пусть имеются игра о поведении потока <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>полной.''' | ||
| Строка 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>-сложной. | ||