algorithm - NP难？在线扑克合谋检测的算法复杂性？

Question

描述拥有 1000 万玩家的在线扑克网站的合谋检测算法复杂性的最佳方式是什么？

假设(我认为这些假设没有太大区别，所以请随意忽略它们，但只是为了澄清一下):

• 该网站拥有 10,000,000 名注册用户。
• 这些玩家总共玩了 50 亿手牌。
• 您获得的唯一信息是该网站的“大师手牌历史数据库”，其中包含所有玩家的底牌和每手牌的下注行动。
• 换句话说，您不能走捷径，例如检查 IP 地址、寻找不寻常的佣金/利润模式等。
• 假设您有一个函数，当传递给一组刚好有 N(其中 N 介于 2 到 10 之间)玩家时，如果该组中的所有玩家都勾结在一起，则返回 TRUE。如果一些但不是所有玩家都是共谋者，则该函数返回 FALSE。返回值为 TRUE 的置信度(例如)为 75%。

您的工作是制作一份包含每个勾结的玩家的详尽列表，以及一份与他勾结的玩家的完整列表。我最近听说这个问题被描述为 NP-hard，但这准确吗？有时我们将仅仅是“难”的东西称为“NP”或“NP-hard”。

谢谢!

Answer 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);
    }
  }
}

我看不出调用 haveColluded 参数数量大于 2 有什么意义，因为这可能会产生漏报。我想这取决于功能的成本。但是上面的结果是 O(n^2) 调用 haveColluded(n 是玩家的数量)。该函数本身看起来是 O(m)，其中 m 是他们一起玩的游戏数。因此，该算法在 O(n^3) 下看起来很好。要成为 NP-hard，您必须证明“问题 H 是 NP-hard 当且仅当存在 NP-完全问题 L 是多项式时间图灵可简化为 H [...] 换句话说，L 可以由具有 H 的预言机的预言机在多项式时间内求解。” (http://en.wikipedia.org/wiki/NP-hard)。我研究过 NP 完全问题(例如 3-SAT、旅行商问题等)，但我不知道您如何证明这一点。但话又说回来，它确实与 clique problem 可疑地相似。 .