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

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

मधु सूदनहार्वर्ड विश्वविद्यालय के एक कंप्यूटर वैज्ञानिक, जिन्होंने 2002 का रॉल्फ नेवानलिन्ना पुरस्कार (जिसे अब अबेकस पुरस्कार कहा जाता है) जीता, ने कहा कि क्षेत्र पर विगडरसन के प्रभाव को नजरअंदाज करना असंभव है। सूडान ने कहा, "एवी के काम से वास्तव में जुड़े बिना कंप्यूटर विज्ञान के किसी भी क्षेत्र में काम करना बहुत कठिन है।" "और हर जगह, आपको बहुत गहरी अंतर्दृष्टि मिलती है।" उदाहरण के लिए, 1980 के दशक के उत्तरार्ध में, सूडान ने कुछ गणितीय कार्यों और बहुपदों के बीच संबंधों की जांच करने वाले एक पेपर पर विगडरसन के साथ काम किया। उस काम ने सूडान के पूरे करियर की शुरुआत की। सूडान ने कहा, "यह एवी के लिए विशिष्ट है।" "वह कुछ जगह पर पहुंच जाता है, वह सही सवाल पूछता है और फिर वह आगे बढ़ जाता है।"

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

उन्हें एक ऐसा क्षेत्र मिला जो गहरे, अनुत्तरित प्रश्नों से समृद्ध था जो मूलतः गणितीय थे। उनके सबसे शुरुआती प्रयासों में से एक एक प्रतीत होने वाले विरोधाभास पर केंद्रित था: क्या किसी और को यह समझाना संभव था कि एक गणितीय कथन बिना बताए सिद्ध किया गया था।

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

“क्रिप्टोग्राफी में यह एक महत्वपूर्ण परिणाम है; यह अत्यंत केंद्रीय है,'' रज़ ने कहा। शून्य-ज्ञान प्रमाण का उपयोग करके, कोई यह साबित कर सकता है कि उन्होंने अपनी गुप्त कुंजी का उपयोग करके किसी संदेश को सही ढंग से एन्क्रिप्ट किया है या उस पर हस्ताक्षर किए हैं, इसके बारे में कोई भी जानकारी बताए बिना। "एवी के पास क्रिप्टोग्राफी में कुछ अत्यंत महत्वपूर्ण परिणाम हैं, और यह उनमें से सबसे महत्वपूर्ण हो सकता है।"

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

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

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

एक के लिए 1994 कागज, उन्होंने और कंप्यूटर वैज्ञानिक नोम निसान ने उस संबंध पर प्रकाश डाला। उन्होंने साबित कर दिया कि यदि कोई प्राकृतिक कठिन समस्या मौजूद है, जैसा कि अधिकांश कंप्यूटर वैज्ञानिकों को संदेह है, तो प्रत्येक कुशल यादृच्छिक एल्गोरिदम को एक कुशल नियतात्मक द्वारा प्रतिस्थापित किया जा सकता है। विग्डरसन ने कहा, "आप हमेशा यादृच्छिकता को खत्म कर सकते हैं।"

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

सूडान ने कहा कि पेपर ने कंप्यूटर वैज्ञानिकों को यादृच्छिकता की डिग्री पहचानने में मदद की जो कठिन समस्याओं की जटिलताओं को प्रकट करने और उन्हें हल करने में मदद कर सकती है। "यह सिर्फ यादृच्छिकता नहीं है बल्कि यादृच्छिकता की धारणा है," उन्होंने कहा। “यही कुंजी है।”

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

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

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