4511
правок
Сложность ядра: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 66: | Строка 66: | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1. Пусть имеются игра о | Теорема 1. Пусть имеются игра о поведении потока Fj = (E,v), заданная на сети D = (V;E;!;s; t) и вектор x E !>■ R+ с x(E) = v(E). Задача о существовании коалиции S С N, такой, что x(S) < v(S), является NP-полной. Другими словами, проверка принадлежности к ядру для игр о поведении потока является co-NP-полной. | ||