एनपी-हार्ड? ऑनलाइन पोकर संलयन पहचान की एल्गोरिदमिक जटिलता?

Question

दस मिलियन-खिलाड़ी ऑनलाइन पोकर साइट के लिए टकराव का पता लगाने की एल्गोरिदमिक जटिलता का वर्णन करने का सबसे अच्छा तरीका क्या है?

मान लें (मुझे नहीं लगता कि इन मान्यताओं ज्यादा फर्क तो उन्हें अनदेखा करने के लिए स्वतंत्र लग रहा है, लेकिन सिर्फ स्पष्ट करने के लिए):

• कि साइट 10,000,000 पंजीकृत उपयोगकर्ता ही है।
• कि इन खिलाड़ियों ने कुल 5 अरब हाथ खेले हैं।
• कि आपको दी गई एकमात्र जानकारी साइट के लिए "मास्टर हैंड हिस्ट्री डेटाबेस" है, जिसमें प्रत्येक खिलाड़ी के लिए सभी खिलाड़ी छेद कार्ड और सट्टेबाजी कार्य शामिल हैं।
• दूसरे शब्दों में, आप शॉर्टकट नहीं ले सकते हैं जैसे आईपी पते की जांच करना, असामान्य रेक/लाभ पैटर्न की तलाश करना, और आगे।
• मान लीजिए कि आपको एक ऐसा फ़ंक्शन दिया गया है, जब वास्तव में एन (जहां एन 2 और 10 के बीच है) के समूह को पारित किया जाता है, तो समूह में सभी खिलाड़ियों ने एक साथ तालमेल किया है, तो सत्य लौटाता है। अगर कुछ खिलाड़ी नहीं हैं लेकिन सभी खिलाड़ी कॉलर हैं, तो फ़ंक्शन गलत हो जाता है। TRUE का एक वापसी मूल्य (उदाहरण के लिए) 75% आत्मविश्वास से बना है।

आपका काम उन खिलाड़ियों की पूरी सूची तैयार करने के साथ-साथ उन सभी खिलाड़ियों की एक विस्तृत सूची तैयार करना है, जिनके साथ उन्होंने टक्कर ली है। मैंने हाल ही में एनपी-हार्ड के रूप में वर्णित इस समस्या को सुना है लेकिन क्या यह सही है? कभी-कभी हम चीजें "एनपी" या "एनपी-हार्ड" कहते हैं जो केवल "कठिन" होती हैं।

धन्यवाद!

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 की तुलना में बड़ा तर्क मायने रखता है के साथ haveColluded कॉल करना है कि क्योंकि मिथ्या नकारात्मक दे सकता है एक बिंदु नहीं दिख रहा। मुझे लगता है कि यह इस बात पर निर्भर करता है कि समारोह कितना महंगा है। लेकिन ओ (एन^2) में उपर्युक्त परिणाम कॉल करने के लिए कहते हैं (एन खिलाड़ियों की संख्या)। यह कार्य स्वयं ओ (एम) होगा, जहां एम एक साथ खेले जाने वाले खेलों की संख्या है। इस प्रकार, एल्गोरिदम ओ (एन^3) के तहत अच्छी तरह से लगता है। एनपी-हार्ड होने के लिए, आपको साबित करना होगा "एक समस्या एच एनपी-हार्ड है अगर केवल एक एनपी-पूर्ण समस्या है जो एल बहुपद समय है एच को ट्यूरिंग-कम करने योग्य [...] दूसरे शब्दों में, एल कर सकते हैं एच के लिए एक ओरेकल के साथ एक ओरेकल मशीन द्वारा बहुपद समय में हल किया जाना चाहिए। " (http://en.wikipedia.org/wiki/NP-hard)। मैंने एनपी-पूर्ण समस्याओं का अध्ययन किया है (उदाहरण के लिए 3-एसएटी, यात्रा विक्रेता समस्या, इत्यादि) और मुझे नहीं लगता कि आप इसे कैसे साबित करेंगे। लेकिन फिर, यह clique problem के समान संदिग्ध प्रतीत होता है।

Answer 2

clique detection जैसा लगता है, जो एनपी-हार्ड है। दूसरी ओर, यहां का आकार का आकार सीमित है (10), इसलिए क्रूर-बल एन^10 सबसे खराब है।

संपादित करें: यहां मुख्य प्रश्न यह है कि संलयन कार्य के गुण क्या हैं। क्या फंक्शन को दो छोटे सेटों (5 कहें) खिलाड़ियों को कॉल करके हमेशा एक साथ मिलकर 10 खिलाड़ियों का पता लगाया जा सकता है?

Answer 3

अपने मॉडल के तहत, जो आप वर्णन करते हैं वह काफी आसान होना चाहिए। आपको एक अंतर्निहित ग्राफ दिया जाता है (शिखर खिलाड़ी खिलाड़ी होते हैं, किनारों को एक साथ खेल खेला जाता है)। आप उस ग्राफ का सबग्राफ चाहते हैं।

यदि संलयन फ़ंक्शन पूरी तरह विश्वसनीय था तो आप इसे ग्राफ में प्रत्येक जोड़ी के शीर्ष पर कॉल करते हैं, और आपको उप-अनुच्छेद मिलता है।

वह सबग्राफ शायद काफी डिस्कनेक्ट हो गया है। मैं उम्मीद करता हूं कि परिणामी ग्राफ डिस्कनेक्ट हो जाएगा या बहुत कमजोर रूप से जुड़ा होगा; कुछ अच्छी तरह से जुड़े सबग्राफ कुछ मिनट-कटौती करके जल्दी से गिर जाएंगे।

ध्यान दें कि हम खुद ही जोड़े को देख करने के लिए, सीमित कर सकते हैं क्योंकि मिलीभगत समारोह का पालन करना चाहिए (आत्मविश्वास का स्तर के संदर्भ में) collude (ए, बी, सी) < collude (ए, बी)।

इस वैश्विक संलयन समारोह का निर्माण करना वह हिस्सा है जो कठिन लगता है।

Answer 4

मैं दो कदम में इस विभाजित होगा: प्रत्येक हाथ में खेलने की जांच पोकर के

1. दोहराएं 5 अरब से अधिक हाथ। कुछ एल्गोरिदम को नियोजित करें, चलिए इसे प्रत्येक हाथ पर एल्गोरिदम ए पर कॉल करें। जैसे ही आप जाते हैं, आप एक संलयन ग्राफ बनाते हैं जहां चरम खिलाड़ी खिलाड़ियों का प्रतिनिधित्व करते हैं और अप्रत्यक्ष भारित किनारों में दो खिलाड़ियों के बीच मिलन के कुछ विश्वास का प्रतिनिधित्व होता है। जब एल्गोरिदम ए खिलाड़ी वाई के साथ तालमेल करने वाले खिलाड़ी एक्स के संदेह पर ट्रिगर्स, कुछ मूल्य को संकुचित ग्राफ में भारित किनारे XY में जोड़ा जाता है। जैसे ही आप हाथों से प्रगति करते हैं, किनारे के वजन के साथ समय के साथ जमा होता है। जब कुछ सीमा तक पहुँच गया है, तो बढ़त एक्स और वाई के बीच मिलीभगत

2. तब समारोह निर्धारित करता है कि एन खिलाड़ी कोने की एक सूची सभी एक साथ सांठगांठ है एन कोने युक्त subgraph की पुष्टि करने की बात है का प्रतिनिधित्व करता है पूरी तरह से जुड़ा हुआ है (जिसका मतलब है कि प्रत्येक नोड में सबग्राफ में हर दूसरे नोड को टकराव की सीमा से अधिक वजन होता है)। आईआईआरसी, यह निर्धारित करना ओ (एन * एलजी (एन)) है।