एक आसान-सी लगने वाली समस्या हमारे ब्रह्मांड के लिए बहुत बड़ी संख्याएँ उत्पन्न करती है | क्वांटा पत्रिका

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

यह काफी सरल लगता है. "आप प्राथमिक विद्यालय में जा सकते हैं और बच्चों को यह बता सकते हैं," कहा क्रिस्टोफ़ हासेऑक्सफ़ोर्ड विश्वविद्यालय में एक कंप्यूटर वैज्ञानिक। "लोग सोचेंगे, 'यह आसान होना चाहिए।'"

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

यह पता चलता है कि यह बच्चों जैसी समस्या बेतुकी, लगभग कार्टून जैसी जटिल है - इतनी जटिल कि व्यावहारिक रूप से अन्य सभी प्रसिद्ध कठिन कम्प्यूटेशनल समस्याएं ऐसा लग रहा है, ठीक है, बच्चों का खेल है। इस समस्या को हल करने के लिए आवश्यक प्रयास को मापने का प्रयास करें, और जल्द ही आपको इतनी बड़ी संख्याओं का सामना करना पड़ेगा कि उनके अंक गिनने पर भी आप उन संख्याओं तक पहुंच जाएंगे जिनके बारे में आपने कभी नहीं सुना होगा। ऐसी संख्याएँ अक्सर ब्रह्मांड के पैमाने पर तुलना को आमंत्रित करती हैं, लेकिन वे उपमाएँ भी कम पड़ जाती हैं। “यह न्याय नहीं होगा,” कहा जॉर्ज ज़ेत्शे, जर्मनी के कैसरस्लॉटर्न में मैक्स प्लैंक इंस्टीट्यूट फॉर सॉफ्टवेयर सिस्टम्स में एक कंप्यूटर वैज्ञानिक। "ब्रह्मांड बहुत छोटा है।"

पहुँच में?

इसके मूल में, रीचैबिलिटी समस्या गणितीय वस्तुओं के बारे में है जिन्हें वेक्टर कहा जाता है, जो संख्याओं की क्रमबद्ध सूचियां हैं। इन सूचियों में प्रविष्टियों को घटक कहा जाता है, और एक वेक्टर में घटकों की संख्या को इसकी आयामीता कहा जाता है। उदाहरण के लिए, ऐलिस की फलों की सूची को चार-आयामी वेक्टर द्वारा वर्णित किया जा सकता है (a, b, c, d), जिसके घटक दर्शाते हैं कि किसी भी समय उसके पास कितने सेब, केले, खरबूजे और संतरे हैं।

एक वेक्टर जोड़ प्रणाली, या वीएएस, एक प्रणाली में राज्यों के बीच संभावित बदलावों का प्रतिनिधित्व करने वाले वैक्टर का एक संग्रह है। ऐलिस के लिए, संक्रमण वेक्टर (−1, −1, 1, 0) एक खरबूजे के लिए एक सेब और एक केले के आदान-प्रदान का प्रतिनिधित्व करेगा। वीएएस रीचैबिलिटी समस्या पूछती है कि क्या अनुमत संक्रमणों का कोई संयोजन है जो आपको एक विशिष्ट प्रारंभिक स्थिति से एक विशिष्ट लक्ष्य स्थिति तक ले जा सकता है - या, गणितीय शब्दों में, क्या संक्रमण वैक्टर का कोई योग है जो शुरुआती वेक्टर को लक्ष्य वेक्टर में बदल देता है। बस एक ही समस्या है: सिस्टम की स्थिति का वर्णन करने वाले वेक्टर का कोई भी घटक कभी भी शून्य से नीचे नहीं गिर सकता है।

"यह वास्तविकता के मॉडल के लिए एक बहुत ही स्वाभाविक प्रतिबंध है," कहा वोज्शिएक ज़ेरविंस्की, वारसॉ विश्वविद्यालय में एक कंप्यूटर वैज्ञानिक। "आपके पास सेबों की ऋणात्मक संख्या नहीं हो सकती।"

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

उस प्रश्न का उत्तर देने के लिए, शोधकर्ता दो पूरक दृष्टिकोणों का उपयोग करते हैं। सबसे पहले, वे विशेष रूप से मुश्किल वेक्टर जोड़ प्रणालियों के उदाहरणों की खोज करते हैं जिनमें पहुंच योग्यता निर्धारित करने के लिए कुछ न्यूनतम स्तर के प्रयास की आवश्यकता होती है। समस्या की जटिलता पर उन न्यूनतम स्तरों को "निचली सीमा" कहा जाता है - वे शोधकर्ताओं से कहते हैं, "किसी दिए गए के लिए सबसे पेचीदा सिस्टम n क्या ये कम से कम इतने कठिन हैं।”

दूसरा, शोधकर्ता "ऊपरी सीमाएं" स्थापित करने का प्रयास करते हैं - सबसे शैतानी प्रणालियों में भी पहुंच कितनी कठिन हो सकती है, इसकी सीमाएं। ये कहते हैं, “किसी दिए गए मामले में सबसे पेचीदा उदाहरण n अधिक से अधिक यही कठिन हैं।” सटीक रूप से यह निर्धारित करने के लिए कि सबसे कठिन प्रणालियों में पहुंच कितनी कठिन है, शोधकर्ता निचली सीमाओं को ऊपर और ऊपरी सीमाओं को तब तक नीचे धकेलने का प्रयास करते हैं जब तक वे मिल न जाएं।

बुरे सपने की सामग्री

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

1976 में, कंप्यूटर वैज्ञानिक रिचर्ड लिप्टन वीएएस रीचैबिलिटी समस्या की जटिलता को समझने की दिशा में पहला कदम उठाया। उन्होंने सिस्टम के निर्माण के लिए एक प्रक्रिया विकसित की जिसमें यह निर्धारित करने का सबसे तेज़ तरीका है कि एक राज्य दूसरे से पहुंच योग्य है या नहीं, उनके बीच संक्रमण के अनुक्रम को मैप करना है। इससे उन्हें पहुंच योग्यता समस्या की कठिनाई के माप के रूप में दो सावधानीपूर्वक चुने गए राज्यों के बीच सबसे छोटे पथ की लंबाई का उपयोग करने की अनुमति मिली।

फिर लिप्टन साबित वह आकार की एक प्रणाली का निर्माण कर सकता था n जिसमें दो राज्यों के बीच सबसे छोटे पथ में $latex 2^{2^n}$ से अधिक संक्रमण शामिल थे। इसका तात्पर्य उसके सिस्टम में पहुंच क्षमता निर्धारित करने के लिए आवश्यक प्रयास पर एक समान दोहरी घातीय निचली सीमा है। यह एक चौंकाने वाली खोज थी - दोगुनी घातीय वृद्धि कंप्यूटर वैज्ञानिकों के लिए दुःस्वप्न है। वास्तव में, शोधकर्ता अक्सर सामान्य घातीय वृद्धि पर भी कतराते हैं, जो तुलना में कम है: $latex {2^5}= 32$, लेकिन $latex 2^{2^5}$ 4 बिलियन से अधिक है।

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

लिप्टन ने कहा, "मैंने निश्चित रूप से इसके बारे में बार-बार सोचा।" "लेकिन कुछ समय बाद मैंने हार मान ली और जहां तक ​​मैं बता सकता हूं पिछले 40 वर्षों तक किसी ने कोई प्रगति नहीं की।"

2015 में, कंप्यूटर वैज्ञानिक जेरोम लेरौक्स और सिल्वेन शमित्ज़ अंततः स्थापित एक मात्रात्मक ऊपरी सीमा - इतना ऊँचा कि शोधकर्ताओं ने मान लिया कि यह केवल पहला कदम था जिसे लिप्टन की निचली सीमा तक पहुँचने के लिए नीचे धकेला जा सकता था।

लेकिन ऐसा नहीं हुआ. 2019 में, शोधकर्ताओं ने दशकों के पारंपरिक ज्ञान को उलटते हुए, लिप्टन की तुलना में कहीं अधिक निचली सीमा की खोज की। वीएएस पहुंच योग्यता समस्या किसी के अनुमान से कहीं अधिक जटिल थी।

शक्तियों का एक टॉवर

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

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

कुछ महीनों के बाद उनकी मेहनत रंग लाई. ज़ेरविंस्की और उनके सहयोगी साबित वे वेक्टर जोड़ प्रणालियों का निर्माण कर सकते हैं जिसमें दो राज्यों के बीच का सबसे छोटा रास्ता टेट्रेशन नामक गणितीय ऑपरेशन द्वारा सिस्टम के आकार से संबंधित था जो कि दुःस्वप्न वाली दोहरी घातीय वृद्धि को भी वश में कर देता है।

टेट्रेशन गणित में सबसे परिचित संचालन को जोड़ने वाले पैटर्न का एक सीधा विस्तार है, जो जोड़ से शुरू होता है। एक साथ जोड़ें n किसी संख्या की प्रतिलिपियाँ, और परिणाम उस संख्या को गुणा करने के बराबर होता है n. यदि आप एक साथ गुणा करते हैं n किसी संख्या की प्रतियां, जो घातांक के बराबर है, या संख्या को बढ़ाने के बराबर है nवें शक्ति. टेट्रेशन, जिसे अक्सर ऊपर की ओर इशारा करते हुए तीरों की एक जोड़ी द्वारा दर्शाया जाता है, इस क्रम में अगला चरण है: किसी संख्या को टेट्रेट करना n इसका अर्थ है इसे घातांकित करना n शक्तियों का एक टावर बनाने का समय n ऊंची बातें।

इस बारे में अपना सिर छुपाना मुश्किल है कि टेट्रेशन कितनी जल्दी हाथ से निकल जाता है: $latex 2 uparrowuparrow 3$, या $latex 2^{2^2}$, 16 है, $latex 2 uparrowuparrow 4$ 65,000 से थोड़ा अधिक है, और $latex 2 uparrowuparrow 5$ लगभग 20,000 अंकों वाली एक संख्या है। $लेटेक्स 2 अपअरोअपरो 6$ के सभी अंकों को लिखना शारीरिक रूप से असंभव है - इतने छोटे ब्रह्मांड में रहने का दायित्व।

अपने ऐतिहासिक परिणाम में, ज़ेरविंस्की और उनके सहयोगियों ने साबित कर दिया कि आकार के वेक्टर जोड़ सिस्टम मौजूद हैं n जहां पहुंच क्षमता को निर्धारित करने का सबसे अच्छा तरीका $ लेटेक्स 2 अपररोअपरो एन $ ट्रांज़िशन से अधिक वाले पथ को मैप करना है, जिसका अर्थ है कि एक नई निचली सीमा जिसने लिप्टन को बौना बना दिया है। लेकिन टेट्रेशन जितना सिर चकरा देने वाला है, फिर भी यह समस्या की जटिलता पर अंतिम शब्द नहीं था।

क्विनक्वागिनटिलियन और उससे आगे तक 

वीएएस रीचैबिलिटी, लेरौक्स और शमित्ज़ की जटिलता पर चौंकाने वाली नई निचली सीमा के कुछ ही महीनों बाद नीचे धकेला ऊपरी सीमा उन्होंने तीन साल पहले स्थापित की थी, लेकिन वे टेट्रेशन तक पूरी तरह नीचे नहीं पहुँच पाए। इसके बजाय, उन्होंने साबित कर दिया कि रीचैबिलिटी समस्या की जटिलता एकरमैन फ़ंक्शन नामक गणितीय राक्षसी से तेज़ी से नहीं बढ़ सकती है।

उस फ़ंक्शन को समझने के लिए, टेट्रेशन को उसके गंभीर निष्कर्ष तक परिभाषित करने के लिए उपयोग किए गए पैटर्न को लें। अनुक्रम में अगला ऑपरेशन, जिसे पेंटेशन कहा जाता है, बार-बार टेट्रेशन का प्रतिनिधित्व करता है; इसके बाद बार-बार पेंटेशन के लिए एक और ऑपरेशन (हेक्सेशन) होता है, इत्यादि।

एकरमैन फ़ंक्शन, जिसे $latex A(n)$ कहा जाता है, वह है जो आपको तब मिलता है जब आप संख्या रेखा पर प्रत्येक स्टॉप के साथ संचालन की इस सीढ़ी पर एक कदम आगे बढ़ते हैं: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $लेटेक्स ए(3) = 3^3$, $लेटेक्स ए(4)=4 ऊपर की ओर तीर 4=4^{4^{4^4}}$, और इसी तरह। $latex A(4)$ में अंकों की संख्या अपने आप में एक बहुत बड़ी संख्या है जो लगभग 1 क्विनक्वागिनटिलियन के बराबर है - यह 1 के लिए सनकी और शायद ही कभी आवश्यक नाम है जिसके बाद 153 शून्य होते हैं। "5 के एकरमैन के बारे में चिंता मत करो," सलाह दी जेवियर एस्परज़ाम्यूनिख के तकनीकी विश्वविद्यालय में एक कंप्यूटर वैज्ञानिक।

लेरौक्स और शमित्ज़ के परिणाम ने निचली और ऊपरी सीमा के बीच एक बड़ा अंतर छोड़ दिया - वीएएस रीचैबिलिटी समस्या की सटीक जटिलता सीमा के किसी भी छोर पर या बीच में कहीं भी हो सकती है। ज़ेरविंस्की का उस अंतर को कायम रहने देने का इरादा नहीं था। उन्होंने कहा, "हमने इस पर काम करना जारी रखा क्योंकि यह स्पष्ट था कि यह हमारे जीवन में अब तक की सबसे बड़ी चीज़ है।"

अंतिम सफलता 2021 में मिली, जब ज़ेरविंस्की लुकाज़ ऑर्लिकोव्स्की नामक दूसरे वर्ष के स्नातक छात्र को सलाह दे रहे थे। उन्होंने ऑरलिकोव्स्की को गति देने के लिए समस्या का एक सरल संस्करण सौंपा, और ऑरलिकोव्स्की के काम ने उन दोनों को एक नई तकनीक विकसित करने में मदद की जो सामान्य रीचैबिलिटी समस्या पर भी लागू होती है। इससे उन्हें इसकी इजाजत मिल गयी निचली सीमा को ऊपर उठाएं काफी हद तक - लेरौक्स और शमित्ज़ के एकरमैन की ऊपरी सीमा तक। स्वतंत्र रूप से काम करते हुए, लेरौक्स ने प्राप्त किया एक समतुल्य परिणाम लगभग उसी समय।

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

कभी ख़त्म नहीं हुआ

शोधकर्ताओं ने इसकी सटीक जटिलता का निर्धारण करने के बाद वीएएस रीचैबिलिटी समस्या का अध्ययन करना जारी रखा है, क्योंकि प्रश्न के कई प्रकार अनुत्तरित हैं। उदाहरण के लिए, एकरमैन की ऊपरी और निचली सीमाएँ बढ़ने के विभिन्न तरीकों के बीच अंतर नहीं करती हैं n, जैसे कि वैक्टर की आयामीता बढ़ाना या अनुमत संक्रमणों की संख्या बढ़ाना।

हाल ही में, ज़ेरविंस्की और उनके सहयोगियों ने प्रगति हुई निश्चित आयामीता के साथ वेक्टर जोड़ प्रणालियों के वेरिएंट में जटिलता कितनी तेजी से बढ़ सकती है, इसका अध्ययन करके इन विशिष्ट प्रभावों को अलग करना। लेकिन अभी और किया जाना बाकी है - यहां तक ​​कि तीन आयामों में भी, जहां वेक्टर जोड़ प्रणालियों की कल्पना करना आसान है, पहुंच योग्यता समस्या की सटीक जटिलता अज्ञात बनी हुई है।

माज़ोविकी ने कहा, "एक तरह से, यह हमारे लिए शर्मनाक है।"

शोधकर्ताओं को उम्मीद है कि अपेक्षाकृत सरल मामलों की बेहतर समझ से उन्हें गणना के अन्य मॉडलों का अध्ययन करने के लिए नए उपकरण विकसित करने में मदद मिलेगी जो वेक्टर जोड़ प्रणालियों की तुलना में अधिक विस्तृत हैं। वर्तमान में, हम इन अधिक विस्तृत मॉडलों के बारे में लगभग कुछ भी नहीं जानते हैं।

ज़ेत्शे ने कहा, "मैं इसे कम्प्यूटेबिलिटी को समझने की एक बहुत ही मौलिक खोज के हिस्से के रूप में देखता हूं।"

क्वांटा अपने दर्शकों को बेहतर सेवा देने के लिए सर्वेक्षणों की एक श्रृंखला आयोजित कर रहा है। हमारा ले कंप्यूटर विज्ञान पाठक सर्वेक्षण और आपको निःशुल्क जीतने के लिए प्रवेश दिया जाएगा क्वांटा माल।