🌬️ 👨🏽‍🌾 👲 कंप्यूटर विज्ञान पर प्रमेय का महत्वपूर्ण प्रमाण भौतिकी को गणित के साथ जोड़ देता है 👨🏿‍🔧 🎗️ 🤕

कंप्यूटर विज्ञान के विशेषज्ञों ने कम्प्यूटेशन के माध्यम से सत्यापित ज्ञान में नए सीमाओं की पहचान की है। और साथ ही उन्होंने क्वांटम यांत्रिकी और शुद्ध गणित से महत्वपूर्ण समस्याओं को हल किया।

1935 में, अल्बर्ट आइंस्टीन ने बोरिस पोडोलस्की और नाथन रोसेन के साथ मिलकर उस अवसर का सामना करने की कोशिश की , जो क्वांटम भौतिकी के नए नियमों के साथ खुलता था: दो कणों का "उलझाव", जिसे इस मामले में एक बड़ी दूरी से अलग किया जा सकता है।

अगले वर्ष, एलन ट्यूरिंग ने कम्प्यूटेशन का पहला सामान्यीकृत सिद्धांत तैयार किया और कंप्यूटर के अधीन नहीं, सिद्धांत रूप में समस्याओं के अस्तित्व को साबित किया।

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

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

"यह पूरी तरह से अप्रत्याशित था," मिगुएल नवज़ेक ने कहावियना में क्वांटम ऑप्टिक्स और क्वांटम सूचना संस्थान में क्वांटम भौतिकी का अध्ययन।

प्रमाण के सह-लेखकों ने कम्प्यूटेशनल समस्याओं के समाधान की पुष्टि करने की संभावनाओं की सीमाओं को निर्धारित करने का निर्णय लिया। उनका दृष्टिकोण भ्रम का उपयोग करता है। इन सीमाओं, एक ही समय में शोधकर्ताओं ने लगभग एक पक्ष प्रभाव के रूप में पाया गया है, दो अन्य प्रश्न उत्तर दिया: Zirelson समस्या उलझनों के गणितीय मॉडलिंग के बारे में भौतिक विज्ञान में, और शुद्ध गणित, की समस्या से जूझ रहे कॉन की परिकल्पना घोंसले की।

परिणाम अंततः डोमिनोज़ की तरह गिर गए।

“मूल विचारों के सभी एक ही समय में पैदा हुए थे। यह सुविधाजनक है कि वे सभी इतने अद्भुत तरीके से एक साथ आए, ” हेनरी इवान ने कहाटोरंटो विश्वविद्यालय से, सबूतों के लेखकों में से एक। अन्य लेखक: यूनिवर्सिटी ऑफ टेक्नोलॉजी सिडनी के झेंग्फेंग जी , आनंद नटराजन और कैलिफोर्निया इंस्टीट्यूट ऑफ टेक्नोलॉजी के थॉमस विडिक और ऑस्टिन में टेक्सास यूनिवर्सिटी के जॉन राइट । सभी पांच कंप्यूटर वैज्ञानिक हैं।

अघुलनशील समस्याएं

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

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

“मुझे प्रोग्राम को मैन्युअल रूप से नेल करना है। बस उसे रोको, ”इवान ने कहा।

ट्यूरिंग ने साबित किया कि कोई सामान्य एल्गोरिथ्म नहीं है जो यह निर्धारित कर सकता है कि क्या कोई कार्यक्रम निष्पादन को पूरा करेगा या हमेशा के लिए काम करेगा। यह पता लगाने के लिए, आपको प्रोग्राम को स्वयं चलाना होगा।

इवान, विदिक, जी, नटराजन और राइट

"आपने एक लाख साल इंतजार किया, और कार्यक्रम ने काम नहीं किया। क्या आपको एक और मिलियन वर्ष इंतजार करने की आवश्यकता है? इस सवाल का कोई जवाब नहीं है, ” विलियम स्लोफ़स्ट्रा , वाटरलू विश्वविद्यालय के एक गणितज्ञ ने कहा ।

तकनीकी रूप से, किसी कार्यक्रम को रोकने का काम अकारण है - यहां तक कि सबसे शक्तिशाली कंप्यूटर जिसकी आप कल्पना कर सकते हैं वह हल नहीं कर सकता है।

ट्यूरिंग के बाद, कंप्यूटर वैज्ञानिकों ने उनकी जटिलता के अनुसार अन्य कार्यों को वर्गीकृत करना शुरू किया। अधिक जटिल कार्यों को हल करने के लिए अधिक कंप्यूटिंग संसाधनों की आवश्यकता होती है - काम करने का अधिक समय, अधिक मेमोरी। इसलिए कार्यों की कम्प्यूटेशनल जटिलता का अध्ययन करें।

परिणामस्वरूप, आप प्रत्येक कार्य के बारे में दो प्रश्न पूछ सकते हैं: "इसे हल करना कितना मुश्किल है?" और "कितना मुश्किल यह सही जवाब सत्यापित करने के लिए है?"

पुष्टि के लिए पूछताछ

सरल कार्यों के मामले में, उत्तर को स्वतंत्र रूप से जांचा जा सकता है। लेकिन जैसे-जैसे वे और अधिक जटिल होते जाते हैं, उत्तर की जाँच करना भी एक असंभव कार्य बन सकता है। हालांकि, 1985 में, कंप्यूटर वैज्ञानिकों ने महसूस किया कि उत्तर की शुद्धता को सत्यापित करना संभव था, भले ही इसे स्वयं की पुष्टि करना असंभव हो।

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

सूचना विज्ञान के संदर्भ में, पूछताछ में एक शक्तिशाली कंप्यूटर होता है जो समस्या का समाधान प्रस्तुत करता है - जिसे "कहावत" के रूप में जाना जाता है - और एक कम शक्तिशाली कंप्यूटर, जो प्रश्नों की कहावत को उत्तर की शुद्धता को निर्धारित करने के लिए कहता है, जिसे "परीक्षण" के रूप में जाना जाता है।

एक सरल उदाहरण: कल्पना करें कि आप रंगों में अंतर नहीं करते हैं, और दूसरा व्यक्ति - कहावत - दावा करता है कि कुछ गेंदों में से दो में एक अलग रंग है। आप इस कथन को अपने आप सत्यापित नहीं कर सकते हैं, लेकिन सरल पूछताछ के माध्यम से, आप अभी भी यह सत्यापित कर सकते हैं कि यह सच है।

गेंदों को पीछे रखें और मिश्रण करें। कहावत को पूछें कि कौन सा रंग किसके पास है। यदि वे वास्तव में अलग-अलग रंगों के हैं, तो सवाल का जवाब देने के लिए प्रोवर को लगातार सही ढंग से जवाब देना चाहिए। यदि वे एक ही रंग के होते हैं - अर्थात, वे एक जैसे दिखते हैं - आधे मामलों में कहावत गलत अनुमान व्यक्त करेगी।

"अगर मैं देखता हूं कि आपने आधे मामलों की तुलना में बहुत अधिक सफलता हासिल की है, तो मुझे लगभग यकीन हो जाएगा कि वे एक ही रंग के नहीं हैं," विदिक ने कहा।

नीतिवचन प्रश्न पूछकर, आप अपने द्वारा हल किए जा सकने वाले कार्यों की व्यापक श्रेणी में समाधानों की शुद्धता की पुष्टि कर सकते हैं।

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

“जो लोग इसे जांचते हैं, उनके लिए यह दबाव के लिए अधिक जगह देता है। आप पूछताछ करते हैं, मामले से संबंधित प्रश्न पूछते हैं, जवाबों की जांच करते हैं, ”विदिक ने कहा। यदि संदिग्ध सच कह रहे हैं, तो उनके जवाब ज्यादातर समय में मेल खाना चाहिए। यदि वे झूठ बोलते हैं, तो अधिक विरोधाभास होंगे।

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

कम्प्यूटेशनल जटिलता आपको एक विशुद्ध सैद्धांतिक विचार लग सकता है, लेकिन यह वास्तविक दुनिया से निकटता से संबंधित है। संसाधन कंप्यूटर को समस्याओं को हल करने और निर्णयों की पुष्टि करने की आवश्यकता होती है - समय और स्मृति - मौलिक रूप से भौतिक हैं। इसलिए, भौतिकी में नई खोजें कम्प्यूटेशनल जटिलता को बदल सकती हैं।

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

नया सबूत 21 वीं सदी के कंप्यूटर वैज्ञानिक और 20 वीं सदी के भौतिकी के सबसे अजीब विचारों में से एक के बीच टकराव का अंतिम परिणाम है: उलझाव।

कॉन के घोंसले की परिकल्पना

जब दो कण आपस में उलझ जाते हैं, तो वे एक-दूसरे को प्रभावित नहीं करते हैं - उनका कोई कारण संबंध नहीं है। आइंस्टीन एट अल। 1935 के पेपर में इस विचार को प्रकट किया। उसके बाद, भौतिकविदों और गणितज्ञों ने यह वर्णन करने के गणितीय तरीके के साथ आने का प्रयास किया कि वास्तव में भ्रम का अर्थ क्या है।

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

अप्रत्यक्ष रूप से, इस संभावित असंगति ने शुद्ध गणित के क्षेत्र से एक महत्वपूर्ण समस्या के उद्भव को प्रभावित किया, नेस्टिंग की परिकल्पना। और अंत में, इसने एक विद्वान के रूप में भी काम किया, जिसे पांच कंप्यूटर वैज्ञानिकों ने अपने नए साक्ष्य में लाभ उठाया।

उलझाव को मॉडल करने का पहला तरीका स्थानिक रूप से पृथक कणों की कल्पना करना है। उनमें से एक, उदाहरण के लिए, पृथ्वी पर है, और दूसरा मंगल पर है; उनके बीच की दूरी एक कारण संबंध को छोड़कर। इसे टेंसर उत्पाद मॉडल कहा जाता है।

लेकिन कुछ स्थितियों में, यह पूरी तरह से स्पष्ट नहीं है कि क्या दो वस्तुएं वास्तव में एक-दूसरे से अलग-थलग हैं। इसलिए, गणितज्ञ कार्य-कारण की स्वतंत्रता का वर्णन करने के लिए अधिक सामान्य तरीके से आए हैं।

जब वस्तुओं पर संचालन का क्रम कोई फर्क नहीं पड़ता है, तो ऑपरेशन को स्विच माना जाता है: 3 x 2 2 x 3 के समान होगा। दूसरे मॉडल में, जब उनके गुण सहसंबद्ध होते हैं, तो कण उलझे रहते हैं, लेकिन माप का क्रम कोई फर्क नहीं पड़ता। कण A को कण B, या इसके विपरीत की गति का अनुमान लगाने के लिए मापें। किसी भी मामले में, उत्तर एक ही होगा। इसे स्विच्ड ऑपरेटर उलझाव मॉडल कहा जाता है।

कॉलम और पंक्तियों में आयोजित संख्याओं के उलझाव उपयोग सरणियों के दोनों विवरण - मैट्रिसेस। टेनर उत्पाद मॉडल कॉलम और पंक्तियों की एक सीमित संख्या के साथ मैट्रिक्स का उपयोग करता है। कम्यूटेशन ऑपरेटर उलझाव मॉडल एक अधिक सामान्य वस्तु का उपयोग करता है जो मैट्रिक्स की तरह काम करता है लेकिन इसमें अनंत संख्या में पंक्तियां और कॉलम होते हैं।

समय के साथ, गणितज्ञों ने भौतिकी के साथ उनके कनेक्शन से अलग, इन मैट्रिसेस को अपने दम पर तलाशना शुरू कर दिया। इस काम के ढांचे में, 1976 में गणितज्ञ एलेन कॉन ने परिकल्पना की कि अनंत आयाम वाले कई आयामों को परिमित आयाम के साथ मैट्रिक्स द्वारा अनुमानित किया जा सकता है। यह नेन के घोंसले के शिकार की परिकल्पना के निष्कर्षों में से एक था।

अगले दशक में, सोवियत भौतिक विज्ञानी [मूल भौतिक विज्ञानी में, लेकिन विकिपीडिया पर एक गणितज्ञ / लगभग के रूप में सूचीबद्ध है। अनुवाद।] बोरिस त्सिरलसन ने इस समस्या का अपना संस्करण प्रस्तावित किया, जो फिर से भौतिकी से जुड़ गया। ज़िरलसन ने सुझाव दिया कि उलझाव का वर्णन करने वाले टेनर उत्पाद और कम्यूटेटिव ऑपरेटर मॉडल लगभग बराबर हैं। यह समझ में आता है, क्योंकि सैद्धांतिक रूप से ये एक ही भौतिक घटना का वर्णन करने के दो अलग-अलग तरीके हैं। इसके बाद के कार्यों से पता चला कि मैट्रिस के कनेक्शन और उनका उपयोग करने वाले भौतिक मॉडल के कारण, नेस्टिंग के बारे में कॉन की परिकल्पना और जिरलसन समस्या एक दूसरे से अनुसरण करते हैं: एक को हल करें और आप दूसरे को हल करें।

हालांकि, परिणामस्वरूप दोनों समस्याओं का समाधान पूरी तरह से अलग दिशा में दिखाई दिया।

भौतिकी और खेल

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

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

लेकिन सबसे पहले, यह समझने के लिए कि ये गेम कैसे काम करते हैं, दो खिलाड़ियों, ऐलिस और बॉब और एक 3x3 बॉक्स की कल्पना करें। जज एलिस को एक लाइन देता है और सुझाव देता है कि वह प्रत्येक सेल में 0 या 1 लाइन लगाए ताकि संख्याओं का योग विषम हो। बॉब को एक कॉलम सौंपा गया है, और उसे अपनी सभी कोशिकाओं को भरने की आवश्यकता है ताकि संख्याओं का योग सम हो। वे जीतते हैं यदि वे एक ही संख्या को एक ही सेल में रखते हैं - जहां चयनित पंक्ति और स्तंभ प्रतिच्छेद। लेकिन एक ही समय में वे संवाद नहीं कर सकते।

सामान्य परिस्थितियों में, खिलाड़ियों में से सबसे अच्छा 89% मामलों में जीतने में सक्षम है। लेकिन क्वांटम दुनिया में, वे इस परिणाम में सुधार कर सकते हैं।

मान लीजिए कि ऐलिस और बॉब ने उलझे हुए कणों की एक जोड़ी साझा की। उनमें से प्रत्येक अपने कण का माप लेता है और परिणामों का उपयोग करके यह निर्धारित करता है कि प्रत्येक कोशिका में 0 या 1 लिखना है या नहीं। चूंकि कण उलझे हुए हैं, इसलिए उनके मापन के परिणाम एक-दूसरे के साथ सहसंबद्ध होंगे, जिसका अर्थ है कि उनके उत्तर भी सहसंबंधित होंगे - मतलब , वे 100% मामलों में जीतने में सक्षम होंगे।

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

इवान ने कहा, "लोगों ने वर्षों से इस तरह के प्रयोग किए हैं, और यह इस प्रकार है कि यह भयावह प्रभाव वास्तव में मौजूद है।"

किसी भी खेल का विश्लेषण करते समय, आपको इस बारे में जानकारी की आवश्यकता हो सकती है कि यदि वे सर्वोत्तम संभव तरीके से खेलने की कोशिश करते हैं तो खिलाड़ी कितनी बार गैर-स्थानीय खेल जीतते हैं। उदाहरण के लिए, यदि आप सॉलिटेयर सॉलिटेयर लेते हैं, तो आप उस संभावना की गणना कर सकते हैं जिसके साथ खेलने वाला खिलाड़ी पूरी तरह से जीतने में सक्षम होगा।

लेकिन 2016 में, विलियम स्लॉफ़स्ट्रा ने साबित किया कि गैर-स्थानीय खेलों में जीतने की सटीक अधिकतम संभावना की गणना के लिए कोई सामान्य एल्गोरिथ्म नहीं है। शोधकर्ताओं ने सवाल पूछा: क्या कम से कम जीत की अधिकतम प्रतिशत की भविष्यवाणी करना संभव है?

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

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

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

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

जटिल मदद

2000 के दशक की शुरुआत में, कंप्यूटर वैज्ञानिकों ने सोचा: कार्यों के स्पेक्ट्रम कैसे बदलेंगे, जिनके समाधान की पुष्टि जटिल कणों के साथ दो प्रहरियों के साक्षात्कार से की जा सकती है?

अधिकांश ने फैसला किया कि उलझाव पुष्टि के खिलाफ खेलेंगे। वास्तव में, दो संदिग्धों के लिए एक सुसंगत झूठ का निर्माण करना आसान होगा यदि उनके पास उत्तरों को समन्वयित करने का एक तरीका है।

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

विदिक ने कहा, "भ्रम एक सहसंबंध पाने का एक तरीका है जो उन्हें झूठ बोलने और धोखा देने में मदद करता है।" "लेकिन आप वास्तव में इसे अपने पक्ष में लपेट सकते हैं।"

यह समझने के लिए कि यह कैसे संभव है, आपको पहले उन कार्यों की लगभग अलौकिक श्रेणी का मूल्यांकन करने की आवश्यकता है जिनके समाधान आप इस इंटरैक्टिव प्रक्रिया से जांच सकते हैं।

एक ग्राफ की कल्पना करें - लाइनों (किनारों) से जुड़े बिंदुओं (कोने) का एक सेट। आप यह पता लगाना चाहते हैं कि क्या तीन रंगों के साथ कोने को रंगना संभव है, ताकि एक ही रंग के कोने के जोड़े न हों, एक आम किनारे से एकजुट हो।

यदि आप एक बहुत बड़े ग्राफ को साबित करने वाले कुछ लोगों को देते हैं, और वे कहते हैं कि इसे तीन रंगों में वर्णित किया जा सकता है, तो आप सोचेंगे: क्या इस उत्तर की जांच करने का कोई तरीका है?

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

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

हालांकि, भ्रम साबित करने वाले को खुद से सवाल पूछने की अनुमति देता है।

“समीक्षक को प्रश्नों का पता लगाने की आवश्यकता नहीं है। इंस्पेक्टर खुद को उसके लिए सवालों की गणना करने के लिए साबित करता है, ”राइट ने कहा।

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

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

“हम सभी कामों को विफल करने के लिए भ्रम का उपयोग करने जा रहे हैं। विदिक ने कहा कि हम उन्हें अपने सवाल खुद चुनने देंगे।

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

इवान ने कहा, "अगर गिनती को तीन रंगों में रंगा जा सकता है, तो साबित करने वाले आपको मना सकते हैं।"

यह पता चला है कि यह पुष्टिकरण प्रक्रिया गैर-स्थानीय खेल का एक और उदाहरण है। आपको उनके निर्णय की शुद्धता के बारे में आश्वस्त करके "जीत" प्रदान करता है।

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

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

परिणामों की कैस्केड करें

नए कार्य में, पांच कंप्यूटर वैज्ञानिक यह साबित करते हैं कि जटिल सिद्धों की पूछताछ बंद समस्या सहित अनसुलझी समस्याओं के समाधान की पुष्टि कर सकती है।

इवान ने कहा, "इस मॉडल की सत्यापन क्षमता अद्भुत है।"

हालाँकि, रोक समस्या हल नहीं किया जा सकता। और यह तथ्य प्रमाण को पूरा करने के लिए महत्वपूर्ण हो गया।

मान लीजिए कि आप भ्रमित करने वाले सिद्धों के एक जोड़े को एक कार्यक्रम देते हैं। आप उन्हें यह कहने के लिए कहें कि क्या इसका निष्पादन बंद हो जाएगा। आप विभिन्न गैर-स्थानीय खेलों के माध्यम से उनके उत्तर का परीक्षण करने के लिए तैयार हैं: साबित करने वाले प्रश्न देते हैं और उनके उत्तरों की स्थिरता के आधार पर जीतते हैं।

यदि प्रोग्राम वास्तव में बंद हो जाता है, तो प्रॉवर्स को 100% मामलों में इस गेम को जीतने में सक्षम होना चाहिए - जैसा कि एक ग्राफ के मामले में जो तीन रंगों के साथ रंगा जा सकता है, जब दोषपूर्ण प्रूफ़र्स को दो जुड़े हुए कोने के लिए एक ही रंग देने की आवश्यकता नहीं होती है। यदि कार्यक्रम बंद नहीं होता है, तो साबित करने वालों को केवल मौके से जीतना चाहिए - अर्थात, 50% मामलों में।

इसका मतलब यह है कि यदि कोई आपसे किसी विशेष गैर-स्थानीय गेम के लिए जीतने की अनुमानित अधिकतम संभावना निर्धारित करने के लिए कहता है, तो आपको पहले स्टॉप समस्या को हल करने की आवश्यकता होगी। लेकिन इसे हल करना असंभव है। जिसका अर्थ है कि जीतने की अनुमानित अधिकतम संभावना की गणना करने का कार्य अस्वीकार्य है, जैसा कि रोकने की समस्या है।

और यह बदले में, इसका मतलब है कि ज़िरलसन समस्या का उत्तर नकारात्मक है - उलझाव के दो मॉडल समतुल्य नहीं हैं। यदि वे थे, तो स्कोर के निचले और ऊपरी सीमा को एक साथ कम करना और जीतने की अनुमानित अधिकतम संभावना की गणना करना संभव होगा।

"मैड्रिड के कॉम्प्लूटेंस यूनिवर्सिटी के डेविड पेरेज़-गार्सिया ने कहा," ऐसा एल्गोरिथम नहीं हो सकता है, इसलिए दोनों मॉडल अलग-अलग होने चाहिए।

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

दो जटिलता वर्गों की समानता के साक्ष्य की खोज की प्रक्रिया में, कंप्यूटर वैज्ञानिकों ने साइरेलसन परिकल्पना की मिथ्या साबित की, जो पिछले कार्यों के लिए धन्यवाद, का अर्थ है घोंसले के शिकार के बारे में कॉन परिकल्पना।

प्रासंगिक क्षेत्रों के शोधकर्ताओं के लिए यह एक झटका था कि कंप्यूटर विज्ञान के क्षेत्र से प्रतीत होता है असंबंधित साक्ष्य की प्रक्रिया में ऐसी जटिल समस्याओं के जवाब की पहचान की गई थी।

"जब मैंने एमआईपी * = आरई नामक एक कार्य देखा, तो मैं निश्चित रूप से यह नहीं सोचूंगा कि इसका मेरे काम से कोई लेना-देना है," नेज़ेक्ज़ ने कहा, नेस्ट के बारे में कॉन की परिकल्पना के साथ साइरल्सन परिकल्पना को जोड़ने वाले पिछले काम के सह-लेखक। "यह मेरे लिए एक पूर्ण आश्चर्य के रूप में आया।"

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

"उनके परिणाम से, यह असंभव है," स्लॉफ़स्ट्रा ने कहा।

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

“मैं खुद एक गणितज्ञ नहीं हूँ। मुझे नेस्टिंग के बारे में कॉन की परिकल्पना की प्रारंभिक परिभाषा बहुत अच्छी तरह से समझ में नहीं आती है, ”नटराजन ने कहा।

वे और सह-लेखक सुझाव देते हैं कि गणितज्ञ स्वयं अपने क्षेत्र की भाषा में नए परिणाम का अनुवाद करेंगे। साक्ष्य की घोषणा करने वाले एक लेख में, विदिक ने लिखा: "मुझे इसमें कोई संदेह नहीं है कि विशुद्ध रूप से गणितीय परिणाम प्राप्त करने के लिए जटिलता के सिद्धांत की आवश्यकता नहीं रह जाएगी।"

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

नटराजन ने कहा कि कार्यों की एक बड़ी सूची है, जिसमें दो भ्रामक साबित करने वालों की मदद से पुष्टि प्रक्रिया में क्या अवसर हो सकते हैं, के बारे में पूछा गया है। “अब हम जानते हैं कि कौन से हैं। कहानी खत्म हो गई। ”