मैं एनपी-पूर्ण समस्याओं के लिए सरल एल्गोरिदम में विश्वास क्यों नहीं करता

दूसरे दिन, इस ब्लॉग पर 3-SAT समस्या के लिए प्रस्तावित बहुपद एल्गोरिथ्म के बारे में वैज्ञानिकों को एक खुला पत्र प्रकाशित किया गया था। उस विषय में चर्चा अभी भी बंद है और यह कहना समय से पहले है कि एल्गोरिथ्म में त्रुटियां पाई गई हैं, लेकिन मैं यह लिखना चाहूंगा कि "नागरिक वैज्ञानिक" इस सबूत को जल्दी से सत्यापित करने के लिए लाइन में क्यों नहीं लगते हैं।



लगभग छह महीने पहले, अगस्त 2010 में, यह साबित करने का प्रयास किया गया था कि पी ago एनपी। तब एक गणितज्ञ-ब्लॉगर, स्कॉट ओरोन ने इस साक्ष्य के अपने अविश्वास में निराधार प्रतीत नहीं होने के लिए, अपने घर को इस तथ्य पर सेट किया कि सबूत गलत होगा। शायद मैं कुछ भी नहीं खोता अगर मैं (एक छोटे पैमाने पर) उसके उदाहरण का अनुसरण करता हूं और इस तथ्य को रखता हूं कि वर्तमान एल्गोरिथ्म मेरी कार के लिए गलत है (औरिस 2008 रिलीज)।



मेरी राय में, ओरोंसन ने थोड़ा जोखिम लिया। प्रमाण के लेखक विनोद देओलीकर एक अपेक्षाकृत प्रसिद्ध गणितज्ञ हैं, कार्य पी into एनपी सक्षमता के क्षेत्र में आता है, और इस प्रमाण में स्वयं कई मौलिक नए विचारों का उपयोग किया गया है जो आशा करते हैं कि वे उन कठिनाइयों को दरकिनार करने में मदद करेंगे जो उन लोगों ने साबित करने की कोशिश की। यह तथ्य उसके ऊपर है। वर्तमान साक्ष्य के साथ, स्थिति थोड़ी अलग है।



पहला, जो उसके पक्ष में बोलता है। प्रमाण काफी सक्षम रूप से लिखा गया है, इसके लेखक के पास गणितीय प्रशिक्षण है, और सबसे महत्वपूर्ण बात - एल्गोरिथम के बारे में लेख के अलावा, इसका कार्य कार्यान्वयन है।



अब मैं क्यों नहीं मानता कि यह एल्गोरिथ्म सही हो सकता है।



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



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



विरोधाभास जैसा कि यह लग सकता है, वर्तमान साक्ष्य में विश्वास इस तथ्य से नहीं जोड़ा जाता है कि यह काफी छोटा है: इसके पर्याप्त भागों को आसानी से कई पृष्ठ मिलते हैं। तुलना के लिए, फ़र्मेट के प्रमेय के प्रमाण में 200-300 पृष्ठ लगते हैं, न कि गणित के खंडों से प्रारंभिक जानकारी सहित।



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



- लाइन में पहले से ही दिए गए नंबर होते हैं, इसलिए लाइन के अन्य सेल में यह नंबर नहीं हो सकता है।

- केवल दो नंबर X और Y दो वर्ग कोशिकाओं में खड़े हो सकते हैं, इसलिए ये संख्या अन्य वर्ग कोशिकाओं में नहीं खड़ी हो सकती है।

आदि



इसलिए, अगर सुडोकू सरल है, तो यह पूरी तरह से संभव है कि केवल इन नियमों का उपयोग करके, आप इसे हल कर सकते हैं। लेकिन एक जटिल सुडोकू में, आपको नियमों के बेवकूफ आवेदन के अलावा किसी भी विकल्प पर विचार नहीं करना होगा।



चर्चा की एल्गोरिथ्म के साथ स्थिति लगभग सुडोकू विधि के समान है। इसमें कई नियम हैं जिनके अनुसार हम उन निर्णयों को त्याग देते हैं जो हमारे लिए उपयुक्त नहीं हैं। समस्या यह है कि सुडोकू की तरह, यह 3-सैट कार्य में पर्याप्त नहीं होना चाहिए।



PS कृपया इस पोस्ट को एल्गोरिथ्म का खंडन न मानें। ये सिर्फ विधर्मी कारण हैं कि इस एल्गोरिथ्म को काम क्यों नहीं करना चाहिए। पिछली पोस्ट के लेखक ने कल एक अगली कड़ी प्रकाशित करने का वादा किया था, जिसमें वह टिप्पणियों में प्राप्त सवालों का जवाब देंगे।