एन क्वीन्स समस्या को एनपी-कम्प्लीट के रूप में मान्यता दी गई

1850 में पहेली का पहला संस्करण, जब दो रानियाँ बोर्ड पर पूर्व-स्थापित होती हैं, और खिलाड़ी को शेष रानियों (समस्या के दो समाधानों के लिए, कट के नीचे देखें) की व्यवस्था करनी चाहिए

N क्वीन्स का काम N क्वीन्स को N × N बोर्ड पर रखना है ताकि कोई रानी दूसरे की लड़ाई के तहत न हो, बोर्ड पर कई रानियों को पहले से स्थापित किया गया है। यही है, अंत में, कोई भी दो रानियां एक ही पंक्ति या विकर्ण पर नहीं होनी चाहिए। समस्या को पहली बार 1848 में तैयार किया गया था, और 1850 में वे एक पहेली संस्करण के साथ आए, जब बोर्ड पर एक निश्चित संख्या में रानियों को पहले से रखा गया था, और खिलाड़ी को आराम की व्यवस्था करनी चाहिए, यदि संभव हो तो।

सेंट एंड्रयूज विश्वविद्यालय (स्कॉटलैंड) के शोधकर्ताओं ने एक वैज्ञानिक लेख प्रकाशित किया है जिसमें साबित किया गया है कि एन-क्वींस समस्या न केवल # पी-पूर्ण है, बल्कि एनपी-पूर्ण भी है। इसके अलावा, क्ले इंस्टीट्यूट ऑफ मैथेमेटिक्स (यूएसए) एक लाख डॉलर का भुगतान करने के लिए तैयार है जो इस समस्या के समाधान को एक प्रमाण समस्या P = NP के रूप में अनुकूलित कर सकता है।

जैसा कि आप जानते हैं, जटिलता सिद्धांत में, # पी समस्याओं का एक वर्ग है, जिसका समाधान सफल होने की संख्या है, यानी राज्यों को स्वीकार करने में पूरा करना, कुछ गैर-नियतात्मक ट्यूरिंग मशीन के लिए बहुपदीय समय में काम करने के लिए कम्प्यूटेशनल पथ। वर्ग #P (गणना समस्याएं) की कम्प्यूटेशनल समस्याएं वर्ग NP की संबंधित निर्णय समस्याओं से संबंधित हैं।

वैज्ञानिक ध्यान दें कि यह कार्य किसी को भी, जो शतरंज के खेल के नियमों को जानता है, को इन समस्याओं का सार समझाने के लिए एनपी-पूर्ण कार्यों में सबसे सरल हो सकता है। इस कार्य की एक बहुत ही रोचक कहानी है। एक समय में, उसने गॉस का ध्यान आकर्षित किया, जिसने अपने फैसले में एक छोटी सी गलती भी की थी (8 × 8 बोर्ड पर, उसने 76 फैसले रिपोर्ट किए, लेकिन फिर उसने उनमें से चार को गलत माना, ताकि केवल 72 ही रह गए, और बाद में गॉस ने सभी 92 फैसले स्थापित किए। एक बोर्ड के लिए 8 × 8)।

एन × एन बोर्ड के लिए समस्या के एक सामान्यीकरण ने कई गणितज्ञों का ध्यान आकर्षित किया है। पिछली आधी सदी में, इस समस्या के लिए समर्पित कई दर्जन वैज्ञानिक पत्र प्रकाशित किए गए हैं। उनमें से कम से कम छह को Google विद्वान पर 400 से अधिक बार उद्धृत किया गया है: यह गोलम एंड बॉमर्ट, 1965 है; बिटनर और रीडिंग, 1975; मैकवर्थ एंड फ्रायडर, 1985; मिंटन, जॉनसन, फिलिप्स, और लेयर्ड, 1992; सेलमैन, लेवेस्क और मिशेल, 1992; क्रॉफोर्ड, जिन्सबर्ग, लुक्स और रॉय, 1996।

एन-क्वींस समस्या की जटिलता अक्सर गलत होती है। यहां तक ​​कि बहुतायत से उद्धृत कार्यों में भी, इसे अक्सर एनपी-हार्ड समस्या (एनपी-हार्ड) कहा जाता है, लेकिन यह केवल ऐसा होगा यदि पी = एनपी। वास्तव में, समस्या का कम्प्यूटेशनल संस्करण, अर्थात, एन क्वीन्स के लिए समाधानों की संख्या का निर्धारण, एक क्रम A000170 इंटेगर सीक्वेंस के ऑनलाइन विश्वकोश से है। यह अनुक्रम अब n = 27 के लिए अधिकतम ज्ञात है, जहां समाधानों की संख्या 2.34 × 10 ¹⁷ से अधिक है। समस्या का कोई और प्रभावी समाधान सरल संपूर्ण खोज की तुलना में नहीं जाना जाता है। इसलिए, 2016 में n = 27 के लिए, FPGA पर बड़े पैमाने पर समानांतर खोज का उपयोग किया गया था।

उसी समय, यदि कंप्यूटर 1000 × 1000 सेल बोर्ड पर रानियों के संभावित पदों की गणना करना शुरू कर देता है, तो यह इस कार्य को हमेशा के लिए लोड करेगा। वैज्ञानिकों के अनुसार, यदि कोई इसे हल करने के लिए वास्तव में त्वरित और प्रभावी तरीका ढूंढता है, तो वे क्ले इंस्टीट्यूट ऑफ मैथेमेटिक्स से एक मिलियन डॉलर से अधिक का लाभ उठा पाएंगे। "यदि आप एक कार्यक्रम लिखते हैं जो समस्या को वास्तव में जल्दी से हल कर सकता है, तो आप इसे कई महत्वपूर्ण कार्यों को हल करने के लिए अनुकूलित कर सकते हैं, जो हम हर दिन सामना करते हैं," कंप्यूटर विज्ञान के प्रोफेसर इयान जेंट, वैज्ञानिक कार्य के लेखकों में से एक कहते हैं। "उनमें से तुच्छ समस्याएं हैं, जैसे कि फेसबुक पर अपने दोस्तों का सबसे बड़ा समूह ढूंढना, जो एक-दूसरे को नहीं जानते हैं, या बहुत महत्वपूर्ण कार्य हैं, उदाहरण के लिए, कोड को तोड़ना जो हमारे सभी ऑनलाइन लेनदेन की सुरक्षा सुनिश्चित करते हैं।"

लेकिन ये विशुद्ध रूप से सैद्धांतिक निर्माण हैं। व्यवहार में, किसी ने अभी तक त्वरित और प्रभावी तरीके से एन क्वीन्स की समस्या के समाधान के लिए संपर्क नहीं किया है। इस प्रमाण के लिए कि सभी विकल्पों की एक सरल गणना की तुलना में समस्या को हल करने के लिए अधिक प्रभावी तरीका है, वे एक मिलियन डॉलर देंगे।

जर्नल ऑफ आर्टिफिशियल इंटेलिजेंस रिसर्च (doi: 10.1613 / jair.5512, pdf ) जर्नल में अगस्त 2017 में एक वैज्ञानिक लेख प्रकाशित हुआ था।

---

KDPV के साथ समस्या के लिए PS दो समाधान: