NP-Hard? Algorithmic complexity of online poker collusion detection?
What's the best way to describe the algorithmic complexity of collusion detection for a ten-million-player online poker site?

Assume (I don't think these assumptions make much difference so feel free to ignore them, but just to clarify):

 - That the site has 10,000,000 registered users.
 - That these players have played a total of 5 billion hands.
 - That the only information you're given is the "master hand history database" for the site, containing all player hole cards and betting actions for each hand.
 - In other words, you may NOT take shortcuts such as examining IP addresses, looking for unusual rake/profit patterns, and so forth.
 - Assume you are given a function which, when passed a group of exactly N (where N is between 2 and 10) players, returns TRUE if ALL of the players in the group have colluded TOGETHER. If some but not all of the players are colluders, the function returns FALSE. A return value of TRUE is made with (for example) 75% confidence.

Your job is to produce an exhaustive list of every player who's colluded, along with a complete list of the players he's colluded with. I have recently heard this problem described as NP-hard but is this accurate? Sometimes we call things "NP" or "NP-hard" that are merely "hard".

Thanks!
NP-Hard? Algorithmic complexity of online poker collusion detection?
===

What's the best way to describe the algorithmic complexity of collusion detection for a ten-million-player online poker site?

Assume (I don't think these assumptions make much difference so feel free to ignore them, but just to clarify):

 - That the site has 10,000,000 registered users.
 - That these players have played a total of 5 billion hands.
 - That the only information you're given is the "master hand history database" for the site, containing all player hole cards and betting actions for each hand.
 - In other words, you may NOT take shortcuts such as examining IP addresses, looking for unusual rake/profit patterns, and so forth.
 - Assume you are given a function which, when passed a group of exactly N (where N is between 2 and 10) players, returns TRUE if ALL of the players in the group have colluded TOGETHER. If some but not all of the players are colluders, the function returns FALSE. A return value of TRUE is made with (for example) 75% confidence.

Your job is to produce an exhaustive list of every player who's colluded, along with a complete list of the players he's colluded with. I have recently heard this problem described as NP-hard but is this accurate? Sometimes we call things "NP" or "NP-hard" that are merely "hard".

Thanks!