NP-Hard? Алгоритмическая сложность обнаружения онлайн-покупок в онлайн-покер?

Каков наилучший способ описать алгоритмическую сложность обнаружения сговора для сайта онлайн-покера с десятью миллионами игроков?

Предположим (я не думаю, что эти предположения имеют большое значение, поэтому не стесняйтесь их игнорировать, а просто уточнять):

Что на сайте зарегистрировано 10 000 000 зарегистрированных пользователей.
Что эти игроки сыграли в общей сложности 5 миллиардов рук.
Единственной информацией, которую вы предоставили, является "база данных истории рук" для сайта, содержащая все игровые карты и действия для каждой руки.
Другими словами, вы не можете использовать ярлыки, такие как просмотр IP-адресов, поиск необычных диаграмм rake/profit и т.д.
Предположим, вам предоставлена функция, которая, когда передана группа точно N (где N находится между 2 и 10) игроков, возвращает TRUE, если ВСЕ игроки в группе сговорились ВМЕСТЕ. Если некоторые, но не все игроки, являются комлуляторами, функция возвращает FALSE. Возвращаемое значение TRUE выполняется с (например) уверенностью 75%.

Ваша задача - составить исчерпывающий список каждого игрока, который вступил в сговор, вместе с полным списком игроков, с которыми он вступил в сговор. Недавно я услышал эту проблему, описанную как NP-hard, но это точно? Иногда мы называем вещи "NP" или "NP-hard", которые просто "трудны".

Спасибо!

Ответ 1

Подход грубой силы, который я вижу сразу, следующий:

Set colluders = new Set();
for(Player p1 : allPlayers)
{
  for(Player p2 : allPlayers)
  {
    if(!p1.equals(p2) && haveColluded(p1, p2))
    {
      colluders.add(p1);
      colluders.add(p2);
    }
  }
}

Я не вижу смысла вызывать hasColluded с большим количеством аргументов, чем 2, потому что это может дать ложные отрицания. Я полагаю, хотя это зависит от того, насколько дорого стоит эта функция. Но приведенные выше результаты в O (n ^ 2) требуют toColluded (n - количество игроков). Сама функция, казалось бы, была бы O (m), где m - количество игр, в которые они играли вместе. Таким образом, алгоритм кажется хорошо под O (n ^ 3). Чтобы быть NP-сложным, вам нужно доказать: "Задача H является NP-жесткой тогда и только тогда, когда существует NP-полная задача L, которая является полиномиальным временем, приводимым Тьюрингом к H [...] Иными словами, L может решаться в полиномиальное время машиной оракула с оракулом для H." (http://en.wikipedia.org/wiki/NP-hard). Я изучил NP-полные проблемы (например, 3-SAT, проблема коммивояжера и т.д.), И я не понимаю, как вы это докажете. Но опять же, это похоже подозрительно похоже на проблему clique.

Ответ 2

Похоже, обнаружение клики, которое NP-hard. С другой стороны, размер клики здесь ограничен (10), поэтому грубая сила в худшем случае равна n ^ 10.

Изменить: ключевым вопросом здесь является то, каковы свойства функции сговора. Можно ли обнаружить 10 игроков, сходящихся вместе, путем вызова функции на двух меньших наборах (скажем, 5) игроков?

Ответ 3

Под вашей моделью то, что вы описываете, должно быть довольно простым. Вам дается неявный график (вершины - игроки, края соответствуют тому, что они играли в игру вместе). Вы хотите подграф этого графа.

Если функция сговора была абсолютно надежной, вы просто вызываете ее на каждую пару вершин в графе, и вы получаете подграф.

Этот подграф, вероятно, довольно отключен. Я ожидаю, что полученный граф будет отключен или очень слабо связан; большие хорошо связанные подграфы будут быстро выпадать, выполняя некоторые минимальные разрезы.

Обратите внимание, что мы можем ограничиться рассмотрением только пар, потому что функция сговора должна подчиняться (в терминах уровня достоверности) Collude (A, B, C) < Collude (A, B).

Построение этой глобальной функции сговора - это трудная задача.

Ответ 4

Я разделил бы это на два шага:

Итерируйте более 5 миллиардов рук в покере, исследуя игру в каждой руке. Используйте некоторый алгоритм, позвольте называть его алгоритмом A, с каждой стороны. По мере того как вы идете, вы строите граф сговора, где вершины представляют игроков, а неориентированные взвешенные края представляют некоторую уверенность в сговоре между двумя игроками. Когда алгоритм A вызывает подозрение игрока X, сговорившегося с игроком Y, некоторое значение добавляется к взвешенному краю XY в графе сговора. По мере того, как вы продвигаетесь по рукам, которые были сыграны, весы края накапливаются с течением времени. Когда достигнут некоторый порог, край представляет собой сговор между X и Y.
Тогда функция, определяющая, содержит ли список из N игроков вершин все сгруппированные вместе, является вопросом проверки того, что подграф, содержащий N вершин, полностью связан (что означает, что каждый node имеет вес края больше сговора порог для всех остальных node в подграфе). IIRC, определяя это O (n * lg (n)).