NP-硬？在线扑克共谋检测的算法复杂性？

Question

描述一千万玩家在线扑克网站的共谋检测的算法复杂性的最佳方法是什么？

假设(我不认为这些假设会产生很大的不同,所以可以随意忽略它们,但只是为了澄清):

• 该网站拥有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);
    }
  }
}

我认为没有必要使用大于 2 的参数来调用 hasColluded ，因为这可能会产生误报。我想这取决于该功能的成本有多高。但上面的结果会导致 O(n^2) 调用 hasColluded （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、旅行商问题等），但我不知道你如何证明这一点。但话又说回来，这似乎与派系问题有可疑的相似之处。