कंप्यूटर विज्ञान के क्षेत्र से 30 साल की परिकल्पना को साबित करने के लिए दो पृष्ठ पर्याप्त थे।

"संवेदनशीलता" परिकल्पना ने कई प्रमुख कंप्यूटर वैज्ञानिकों को चकित कर दिया, लेकिन इसके नए साक्ष्य इतने सरल निकले कि एक शोधकर्ता इसे एक ही ट्वीट में कम कर सकता है

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

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

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


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

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

1992 में, जेरूसलम विश्वविद्यालय के हिब्रू विश्वविद्यालय के नोम निसान और अब रटगर्स विश्वविद्यालय में काम करने वाले मारियो स्वेज ने सुझाव दिया कि संवेदनशीलता अभी भी इस मंच में फिट बैठती है। लेकिन कोई भी इसे साबित नहीं कर सका। "यह सवाल है, मैं कहूंगा, बूलियन कार्यों के अध्ययन के क्षेत्र में उत्कृष्ट था," Cenedio ने कहा।

कार्नेगी मेलन यूनिवर्सिटी के रयान ओ'डॉनेल ने कहा, "लोगों ने लंबे, जटिल काम लिखे, बहुत कम प्रगति की कोशिश की।"

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

आरोनसन और ओ'डॉनेल ने जुआन की पुस्तक "संवेदनशीलता की परिकल्पना का प्रमाण" कहा, पाल एर्दो के "स्वर्गीय पुस्तक" की अवधारणा का जिक्र किया, जिसमें भगवान प्रत्येक प्रमेय के आदर्श प्रमाण लिखते हैं। "मेरे लिए यह कल्पना करना कठिन है कि भगवान भी संवेदनशीलता प्रमेय का एक सरल प्रमाण जानते हैं," आरोनसन ने लिखा।

संवेदनशील विषय

कल्पना कीजिए, मैथ्यू ने कहा कि आप बैंक ऋण आवेदन पत्र पर प्रश्नों के साथ एक फॉर्म भर रहे हैं, जिसके उत्तर हां / नहीं हो सकते हैं। जब आप कर रहे हैं, बैंकर परिणामों का मूल्यांकन करेगा और आपको बताएगा कि क्या आप ऋण के लिए उपयुक्त हैं। यह प्रक्रिया एक बूलियन फ़ंक्शन है: आपके उत्तर आने वाले बिट्स हैं, और बैंकर का निर्णय आउटगोइंग है।

यदि आपके आवेदन को अस्वीकार कर दिया गया है, तो आप इस बारे में सोच सकते हैं कि क्या आप एक ही प्रश्न में झूठ बोलकर परिणाम बदल सकते हैं - शायद यह कहकर कि आप प्रति वर्ष $ 50,000 से अधिक कमाते हैं, हालांकि यह ऐसा नहीं है। यदि यह झूठ विचार के परिणाम को बदलता है, तो कंप्यूटर वैज्ञानिक ऐसे बूलियन फ़ंक्शन को "संवेदनशील" एक विशेष बिट के मूल्य पर कॉल करेंगे। यदि, उदाहरण के लिए, आप सात स्थानों में से एक में झूठ बोल सकते हैं, और हर बार परिणाम बदल सकते हैं, तो आपके ऋण आवेदन के मूल्यांकन के बूलियन फ़ंक्शन की संवेदनशीलता सात है।

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


बिट्स के उत्क्रमण के साथ त्रुटियों के लिए सर्किट की संवेदनशीलता की कल्पना करने के लिए, एन-आवक बिट्स को एन-आयामी क्यूब के कोने के निर्देशांक के रूप में दर्शाया जा सकता है। यदि मार्ग 1 का निर्माण करता है, तो हम नीले रंग का रंग करेंगे और यदि 0 है तो लाल।

बीच में छोड़ दिया: इनपुट 011 के साथ एक साधारण बूलियन फ़ंक्शन का आउटपुट क्यूब के शीर्ष पर एक नीली डॉट (0,1,1) द्वारा दर्शाया जा सकता है।
केंद्र: पहले बिट को मोड़ते हुए, हम क्यूब के नीले शीर्ष (1,1,1) पर जाएंगे। फ़ंक्शन इस बिट के व्युत्क्रम के प्रति संवेदनशील नहीं है।
मध्य दाईं ओर: तीसरे बिट को मोड़ते हुए, हम क्यूब के लाल शीर्ष (0,1,0) पर जाएंगे। फ़ंक्शन इस बिट के उलट के प्रति संवेदनशील है।

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

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

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

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

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

"इस सवाल ने लोगों को 30 साल तक जगाए रखा है," आरोनसन ने कहा।

घोल घोलें

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

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


हाल ही में लिस्बन में छुट्टी पर हाओ हुआंग

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

उदाहरण के लिए, चार दो-बिट लाइनें - 00, 01, 10 और 11 - एक दो-आयामी विमान पर एक वर्ग के चार कोनों के अनुरूप हैं: (0,0), (0,1), (1,0) और (1,1)। इसी प्रकार, आठ तीन-बिट तार तीन आयामी घन के आठ कोनों के अनुरूप होते हैं, और इसी तरह, उच्च आयामों के लिए। बूलियन फ़ंक्शन को इन घन कोणों को दो अलग-अलग रंगों के साथ रंगने का नियम माना जा सकता है (उदाहरण के लिए, 0 के लिए लाल और 1 के लिए नीला)।

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

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

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

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

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

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

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

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

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