Reducing CMSO to Unbreakable Graphs Cannot be Computable

द ग्रेट ग्राफ डिटेक्टिव एंड द इम्पॉसिबल शॉर्टकट

कल्पना कीजिए कि आप एक विशाल, उलझे हुए शहर में रहस्य सुलझाने की कोशिश कर रहे हैं एक जासूस हैं। यह शहर इमारतों (वर्टिसेस) को जोड़ने वाली सड़कों (एजेस) से बना है, और आपका काम इसमें छिपे किसी विशिष्ट पैटर्न को खोजना है—शायद किसी विशेष व्यवस्था में इमारतों की एक गुप्त क्लब मीटिंग, या एक ऐसा मार्ग जो हर घर की ठीक एक बार यात्रा करता है। कंप्यूटर विज्ञान की दुनिया में, इस "शहर" को ग्राफ कहा जाता है, और यह "रहस्य" CMSO (काउंटिंग मोनैडिक सेकंड-ऑर्डर लॉजिक) नामक एक विशेष तार्किक भाषा में लिखा गया एक प्रश्न है। यह भाषा लगभग किसी भी संरचनात्मक नियम का वर्णन करने के लिए पर्याप्त शक्तिशाली है, जैसे "क्या शहर जुड़ा हुआ है?" या "क्या हम इमारतों को तीन रंगों से रंग सकते हैं ताकि पड़ोसी एक ही रंग के न हों?"

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

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

पेपर की खोज: वह शॉर्टकट जिसे कैलकुलेट नहीं किया जा सकता

इस पेपर में, कोलिन जेनिएट और रूहानी शर्मा एक आश्चर्यजनक और निर्णायक उत्तर देते हैं: नहीं, हम उस नियम की गणना नहीं कर सकते। वे सिद्ध करते हैं कि ऐसा कंप्यूटर प्रोग्राम बनाना गणितीय रूप से असंभव है जो एक तार्किक पहेली ले और कुशलतापूर्वक हल करने के लिए आवश्यक सटीक "अटूटता" (unbreakability) संख्या प्रदान करे।

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

लेखक दो मुख्य परिदृश्यों का उपयोग करके इसे तोड़ते हैं, जिसमें एक चतुर "ट्रैप" (जाल) रणनीति का उपयोग किया गया है:

1. "P बनाम NP" का जाल: वे एक विशिष्ट प्रकार की पहेली (मैप कलरिंग से संबंधित) को देखते हैं जो कंप्यूटर के लिए हल करना बहुत कठिन माना जाता है (यदि प्रसिद्ध "P ≠ NP" धारणा सत्य है)। वे दिखाते हैं कि यदि एक कंप्यूटर उस अटूटता संख्या की गणना कर सकता, तो यह इन कठिन पलों को हल करना अचानक आसान हो जाता। चूंकि हम मानते हैं कि ये पहेलियाँ कठिन बनी रहनी चाहिए, इसलिए इस संख्या की गणना करना असंभव होना चाहिए। यह कहने जैसा है, "यदि आप एक कागज के हवाई जहाज को उड़ाने के लिए आवश्यक हवा की गति की गणना कर सकते हैं, तो आप एक रॉकेट भी उड़ा सकते हैं।" चूंकि हम रॉकेट नहीं उड़ा सकते, इसलिए हम जानते हैं कि हवा की गति की गणना पहुंच से बाहर है।

2. "समय सीमा" का जाल: वे सरल पहेलियों को भी देखते हैं जो आमतौर पर आसान होती हैं, लेकिन केवल तभी जब आपके पास बहुत समय हो। वे यह भी सिद्ध करते हैं कि इन आसान पहेलियों के लिए भी, यदि आप अटूटता संख्या की गणना कर सकते, तो आप उन्हें तुरंत हल कर सकते। लेकिन हम अन्य गहरी गणितीय सिद्धांतों से जानते हैं कि ये पहेलियाँ हर संभव मामले के लिए तुरंत हल नहीं की जा सकतीं। इसलिए, संख्या की गणना करना असंभव है।

उनके प्रमाण का मूल भाग गणितीय सूत्रों के साथ "लुका-छिपी" का खेल है। वे एक नया, जटिल फॉर्मूला बनाते हैं जो एक भूत की तरह कार्य करता है: यह केवल उन शहरों में प्रकट होता है जो कमजोर (breakable) होते हैं। यदि शहर मजबूत (unbreakable) है, तो भूत गायब हो जाता है, और पहेली सरल (हमेशा गलत/false) हो जाती है। वे फिर एक प्रसिद्ध गणितीय परिणाम (ट्रैखटेनब्रॉट का प्रमेय) का उपयोग करते हैं जो कहता है कि कुछ पहेलियों के लिए, वह सबसे छोटा शहर जहाँ पहेली सत्य है, मनमाने ढंग से विशाल हो सकता है—इतना विशाल कि कोई भी कंप्यूटर उन्हें खोजने के लिए सूची नहीं बना सकता।

इन विचारों को जोड़कर, वे दिखाते हैं कि पहेली को हल करने के लिए आवश्यक "अटूटता संख्या" इन भूतिया शहरों के आकार से जुड़ी हुई है। चूंकि भूतिया शहरों का आकार अनियंत्रित रूप से बड़ा हो सकता है, इसलिए अटूटता संख्या भी अनियंत्रित (uncomputable) होनी चाहिए।

इसका भविष्य के लिए क्या अर्थ है

यह पेपर केवल यह नहीं कहता कि "हमने नियम अभी तक नहीं खोजा है"; यह कहता है कि नियम अस्तित्व में नहीं हो सकता जिसे एक कंप्यूटर कैलकुलेट कर सके। पिछले शोधकर्ताओं का यह प्रमाण कि नियम का अस्तित्व है अभी भी सत्य है, लेकिन यह एक "गैर-रचनात्मक" (non-constructive) सत्य है—एक ऐसा तथ्य जो वास्तविक है लेकिन एल्गोरिदम की पहुंच से हमेशा दूर है।

लेखक अपने निष्कर्षों की सीमाओं के बारे में बहुत स्पष्ट हैं। वे सिद्ध करते हैं कि पैरामीटर $q$ (अटूटता थ्रेशोल्ड) पहेली $\phi$ का एक गणना योग्य फलन (computable function) नहीं हो सकता। इसका अर्थ है कि हालांकि हम जानते हैं कि प्रत्येक पहेली के लिए एक "जादुई संख्या" मौजूद है, हम कभी भी उसे खोजने के लिए एक प्रोग्राम नहीं लिख सकते। यदि हम एक "खराब" संख्या (एक जो बहुत छोटी है) का उपयोग करते हैं, तो हमारा एल्गोरिदम विफल हो जाएगा और गलत उत्तर देगा। यदि हम एक "अच्छी" संख्या का उपयोग करते हैं, तो हम पहेली को हल कर सकते हैं, लेकिन हम पहले से उत्तर जाने बिना यह सुनिश्चित नहीं कर सकते कि हमने सही संख्या ढूंढ ली है।

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