NP-Hard? Sự phức tạp về thuật toán của phát hiện thông đồng poker trực tuyến?

Question

Cách tốt nhất để mô tả sự phức tạp về thuật toán của phát hiện thông đồng cho một trang web poker trực tuyến mười triệu người chơi là gì?

Giả (Tôi không nghĩ rằng các giả định này làm cho nhiều khác biệt vì vậy cảm thấy tự do để bỏ qua chúng, nhưng chỉ cần làm rõ):

• Đó trang web có 10.000.000 người dùng đăng ký.
• Những người chơi này đã chơi tổng cộng 5 tỷ tay.
• Đó là thông tin duy nhất bạn cung cấp là "cơ sở dữ liệu lịch sử tổng thể" cho trang web, chứa tất cả các thẻ lỗ của người chơi và các hành động cá cược cho mỗi bàn tay.
• Nói cách khác, bạn KHÔNG được thực hiện các phím tắt như kiểm tra địa chỉ IP, tìm kiếm các mẫu cào/lợi nhuận bất thường, v.v.
• Giả sử bạn được cung cấp một chức năng, khi chuyển một nhóm chính xác N (trong đó N là từ 2 đến 10) người chơi, trả về TRUE nếu TẤT CẢ người chơi trong nhóm đã cộng tác TOGETHER. Nếu một số nhưng không phải tất cả người chơi đều là đồng nghiệp, hàm trả về FALSE. Giá trị trả về TRUE được thực hiện với (ví dụ) độ tin cậy 75%.

Công việc của bạn là tạo danh sách đầy đủ về mọi người chơi cùng với danh sách đầy đủ các cầu thủ mà anh ấy đã hợp tác. Gần đây tôi đã nghe vấn đề này được mô tả là NP-hard nhưng điều này có chính xác không? Đôi khi chúng ta gọi những thứ "NP" hoặc "NP-hard" chỉ đơn thuần là "cứng".

Cảm ơn!

Answer 1

Phương pháp brute-force Tôi thấy ngay là:

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

Tôi không thấy một điểm để gọi điện thoại haveColluded với số lượng tranh luận lớn hơn 2 bởi vì đó có thể cung cấp âm tính giả. Tôi cho rằng nó phụ thuộc vào chức năng của nó. Nhưng kết quả ở trên trong O (n^2) các cuộc gọi đến haveColluded (n là số lượng người chơi). Bản thân hàm có vẻ là O (m), trong đó m là số lượng trò chơi mà chúng chơi cùng nhau. Do đó, thuật toán có vẻ như cũng trong O (n^3). Để NP-hard, bạn phải chứng minh "Một vấn đề H là NP-cứng nếu và chỉ khi có một vấn đề NP-đầy đủ L đó là thời gian đa thức Turing-reducible H [...] Nói cách khác, L có thể được giải quyết trong thời gian đa thức bởi một máy oracle với một oracle cho H. " (http://en.wikipedia.org/wiki/NP-hard). Tôi đã nghiên cứu các vấn đề NP-complete (ví dụ: 3-SAT, Vấn đề về nhân viên bán hàng du lịch, v.v.) và tôi không thấy cách bạn chứng minh điều đó. Nhưng sau đó một lần nữa, nó có vẻ nghi ngờ tương tự như clique problem.

Answer 2

Có vẻ như clique detection, là NP-hard. Mặt khác, kích thước clique bị hạn chế ở đây (10), do đó, sức mạnh vũ phu là n^10 ở mức tồi tệ nhất.

Chỉnh sửa: Câu hỏi chính ở đây là những thuộc tính của chức năng thông đồng là gì. Có thể 10 người chơi cùng nhau luôn được phát hiện bằng cách gọi chức năng trên hai bộ nhỏ hơn (nói 5) người chơi?

Answer 3

Theo mô hình của bạn, những gì bạn mô tả nên khá dễ dàng. Bạn được đưa ra một đồ thị tiềm ẩn (đỉnh là người chơi, các cạnh tương ứng với việc đã chơi một trò chơi với nhau). Bạn muốn một biểu đồ con của biểu đồ đó.

Nếu chức năng thông đồng hoàn toàn đáng tin cậy, bạn chỉ cần gọi nó trên mọi cặp đỉnh trong biểu đồ và bạn sẽ nhận được biểu đồ con.

Biểu đồ con đó có thể khá bị ngắt kết nối. Tôi mong đợi biểu đồ kết quả bị ngắt kết nối hoặc kết nối rất yếu; các biểu đồ con lớn được kết nối tốt sẽ rơi ra nhanh chóng bằng cách thực hiện một số vết cắt nhỏ.

Lưu ý rằng chúng tôi có thể hạn chế chính mình để nhìn vào chỉ cặp, bởi vì chức năng thông đồng nên vâng lời (về mức độ tin cậy) thông đồng với nhau (A, B, C) < thông đồng (A, B).

Việc xây dựng chức năng thông đồng tổng thể này là một phần có vẻ khó khăn.

Answer 4

tôi sẽ chia thành hai bước:

1. lặp trên 5 tỷ tay chơi poker kiểm tra vở kịch trong mỗi bàn tay. Sử dụng một số thuật toán, hãy gọi nó là thuật toán A, trên mỗi bàn tay. Khi bạn đi, bạn xây dựng một đồ thị thông đồng, nơi các đỉnh đại diện cho người chơi và các cạnh có trọng số không xác định thể hiện sự tự tin của sự thông đồng giữa hai người chơi. Khi thuật toán A gây nên sự nghi ngờ của người chơi X đối chiếu với trình phát Y, một số giá trị được thêm vào XY cạnh có trọng số trong biểu đồ thông đồng. Khi bạn tiến bộ thông qua các bàn tay đã được chơi trọng lượng cạnh tích lũy theo thời gian. Khi một số ngưỡng đã đạt tới, sau đó cạnh đại diện cho thông đồng giữa X và Y.

2. Sau đó, chức năng xác định xem một danh sách các đỉnh máy nghe nhạc N có tất cả thông đồng với nhau là một vấn đề xác minh đồ thị con chứa các đỉnh N được kết nối hoàn toàn (nghĩa là mọi nút có trọng số cạnh lớn hơn ngưỡng kết hợp với mọi nút khác trong đồ thị con). IIRC, xác định đây là O (n * lg (n)).