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

Алгоритмическое исследование ядра представляет собой сложную задачу, поскольку на его определение накладывается экспоненциальное число ограничений. Следующие вопросы о вычислительной сложности привлекли внимание множества исследователей:

'''ИГРА О ПОВЕДЕНИИ ПОТОКА (FLOW GAME)'''. Пусть D = (V, E; <math>\omega</math>; s, t) – ориентированная сеть движения потока, где V – множество вершин, E – множество дуг, <math>\omega : E \to R^+</math> – функция пропускной способности дуги, s и t – источник и сток сети, соответственно. Предположим, что каждый игрок контролирует одну дугу сети. Значение максимального потока можно рассматривать как прибыль, получаемую игроками при сотрудничестве. Тогда игра о поведении потока <math>\Gamma_f = (E, \mathbf{v})</math>, связанная с сетью D, определяется следующим образом:

В работах Кайлая и Земела [6], а также Дена и коллег [2] было показано, что игра о поведении потока является полностью сбалансированной, и поиск члена ядра может быть выполнен за полиномиальное время.