آوی ویگدرسون، پیشگام نظریه پیچیدگی، برنده جایزه تورینگ | مجله کوانتا

برای بیش از 40 سال، Avi Wigderson مسائل را مطالعه کرده است. اما به عنوان یک نظریه پرداز پیچیدگی محاسباتی، او لزوماً به پاسخ این مشکلات اهمیت نمی دهد. او اغلب فقط می خواهد بداند که آیا آنها قابل حل هستند یا نه، و چگونه آنها را تشخیص دهد. گفت: وضعیت مضحک است ویگدرسون، دانشمند کامپیوتر در موسسه مطالعات پیشرفته در پرینستون، نیوجرسی. مهم نیست که یک سوال چقدر سخت به نظر می رسد، یک راه کارآمد برای پاسخ به آن می تواند دور از دسترس پنهان شود. تا آنجا که ما می دانیم، برای هر مشکلی که با آن روبرو هستیم و سعی در حل آن داریم، نمی توانیم رد کنیم که الگوریتمی دارد که بتواند آن را حل کند. این تنها جالب ترین مشکل برای من است.»

امروز ویگدرسون برنده مسابقه معرفی شد جایزه تورینگ AM، که به طور گسترده یکی از افتخارات برتر در علوم کامپیوتر به حساب می آید، به دلیل مشارکت های اساسی او در تئوری محاسبات. کار ویگدرسون تقریباً در همه زمینه‌ها تأثیر گذاشته است. همکاران، همکاران و مربیان او می‌گویند که او همواره پل‌های غیرمنتظره‌ای را بین مناطق مختلف پیدا می‌کند. و کار او در مورد تصادفی و محاسبات، که از دهه 1990 شروع شد، ارتباطات عمیقی را بین ریاضیات و علوم کامپیوتر نشان داد که زیربنای تحقیقات امروزی است.

مادو سودانیک دانشمند کامپیوتر در دانشگاه هاروارد که در سال 2002 جایزه رولف نوانلینا (که اکنون جایزه آباکوس نامیده می شود) را از آن خود کرد، گفت که نمی توان تأثیر ویگدرسون را در این زمینه از دست داد. سودان گفت: «کار کردن در هر فضایی در علوم کامپیوتر بدون تداخل با کارهای آوی بسیار سخت است. "و در همه جا، بینش های بسیار عمیقی پیدا می کنید." به عنوان مثال، در اواخر دهه 1980، سودان با ویگدرسون روی مقاله ای کار کرد که ارتباط بین برخی از توابع ریاضی و چند جمله ای ها را بررسی می کرد. این کار کل حرفه سودان را آغاز کرد. سودان گفت: «این برای آوی معمولی است. او وارد فضایی می‌شود، سؤالات درستی می‌پرسد و سپس ادامه می‌دهد.»

ویگدرسون در حیفا، اسرائیل، به عنوان یکی از سه پسر یک پرستار و یک مهندس برق، که هر دو از هولوکاست جان سالم به در بردند، بزرگ شد. پدرش عاشق پازل بود و علاقه شدیدی به ایده های اساسی در ریاضی داشت که با فرزندانش در میان می گذاشت. ویگدرسون گفت: "او کسی است که من به این ویروس مبتلا شدم." زمانی که در دهه 1970 کالج را در تکنیون در حیفا شروع کرد، می‌خواست در رشته ریاضی تحصیل کند، اما والدینش او را در عوض به سمت علوم کامپیوتر هدایت کردند. او گفت: «آنها فکر می کردند شاید این ایده خوبی بود که وقتی کارم تمام شد، کار داشته باشم.

او میدانی سرشار از سؤالات عمیق و بی پاسخی یافت که در قلبشان ریاضی بود. یکی از اولین تلاش‌های پیشگامانه او بر یک تناقض ظاهری متمرکز بود: اینکه آیا می‌توان شخص دیگری را متقاعد کرد که یک گزاره ریاضی بدون نشان دادن چگونگی اثبات شده است.

گفت: "کسی که مدرک را می بیند، چیزی در مورد خود اثبات نمی آموزد." ران راز، دانشمند کامپیوتر در دانشگاه پرینستون. در سال 1985، شفی گلدواسر، سیلویو میکالی و چارلز راکف این مفهوم را معرفی کردند. اثبات های تعاملی دانش صفر، استفاده از آن را برای چند عبارت نشان می دهد. ویگدرسون، همراه با میکالی و اودد گلدریچ، بعداً این ایده را توضیح دادند و شرایطی را ارائه کردند که نشان می‌داد اگر یک جمله قابل اثبات باشد، همچنین دارای اثبات دانش صفر است.

این یک نتیجه کلیدی در رمزنگاری است. راز گفت که بسیار مرکزی است. با استفاده از اثبات دانش صفر، کسی می تواند ثابت کند که پیامی را به درستی رمزگذاری کرده یا با استفاده از کلید مخفی خود امضا کرده است، بدون اینکه اطلاعاتی در مورد آن فاش شود. Avi نتایج بسیار مهمی در رمزنگاری دارد و این ممکن است مهمترین آنها باشد.

اما شاید اساسی ترین نتیجه ویگدرسون در زمینه دیگری نهفته است: پیوند سختی محاسباتی به تصادفی بودن. در اواخر دهه 1970، دانشمندان کامپیوتر متوجه شده بودند که برای بسیاری از مسائل سخت، الگوریتم‌هایی که از تصادفی بودن استفاده می‌کنند، که الگوریتم‌های احتمالی نیز نامیده می‌شوند، می‌توانند تا حد زیادی از جایگزین‌های قطعی خود پیشی بگیرند. در یک 1977 اثباتبرای مثال، رابرت سولووی و ولکر استراسن الگوریتم تصادفی‌سازی شده‌ای را معرفی کردند که می‌توانست تعیین کند که آیا عدد اول سریع‌تر از بهترین الگوریتم‌های قطعی آن زمان است یا خیر.

برای برخی مسائل، الگوریتم‌های احتمالی می‌توانند به الگوریتم‌های قطعی اشاره کنند. در اوایل دهه 1980، ویگدرسون با ریچارد کارپ از دانشگاه کالیفرنیا، برکلی، کار کرد تا ایده تصادفی بودن را به مسائلی که از نظر محاسباتی سخت تلقی می‌شوند مرتبط کند، به این معنی که هیچ الگوریتم قطعی شناخته شده‌ای نمی‌تواند آنها را در مدت زمان معقولی حل کند. ویگدرسون گفت: "ما نمی دانیم چگونه ثابت کنیم آنها سخت هستند." با این حال، او و کارپ یک الگوریتم تصادفی شده برای یک مسئله سخت خاص پیدا کردند که بعداً توانستند آن را غیر تصادفی کنند و به طور موثر یک الگوریتم قطعی برای آن کشف کردند. تقریباً در همان زمان، سایر محققان نشان دادند که چگونه مفروضات سختی محاسباتی در مسائل رمزنگاری می‌توانند به طور کلی تصادفی‌سازی را فعال کنند.

اثربخشی نامعقول تصادفی بودن او را به تفکر در مورد ماهیت خود تصادفی سوق داد. او مانند سایر محققان در آن زمان این سوال را مطرح کرد که چقدر برای حل کارآمد مسئله ضروری است و تحت چه شرایطی می توان آن را به طور کلی حذف کرد. او گفت: «در ابتدا، مشخص نبود که اگر این فقط حماقت خودمان بود، که نمی‌توانیم تصادفی بودن را حذف کنیم. "اما سوال بزرگتر این بود که آیا تصادفی بودن همیشه می تواند به طور موثر حذف شود یا خیر." او متوجه شد که نیاز به تصادفی بودن با دشواری محاسباتی مسئله ارتباط تنگاتنگی دارد.

برای مقاله 1994او و دانشمند کامپیوتر نوام نیسان این ارتباط را روشن کردند. آنها ثابت کردند که اگر هر گونه مشکل سخت طبیعی وجود داشته باشد، همانطور که اکثر دانشمندان رایانه گمان می کنند، هر الگوریتم تصادفی کارآمد را می توان با یک الگوریتم قطعی کارآمد جایگزین کرد. ویگدرسون گفت: "شما همیشه می توانید تصادفی بودن را از بین ببرید."

نکته مهم این است که آنها دریافتند که الگوریتم‌های قطعی ممکن است از توالی‌های «شبه تصادفی» استفاده کنند - رشته‌هایی از داده‌هایی که تصادفی به نظر می‌رسند اما اینطور نیستند. آنها همچنین نشان دادند که چگونه می توان از هر مشکل سخت برای ساخت یک ژنراتور شبه تصادفی استفاده کرد. تغذیه بیت های شبه تصادفی (به جای نمونه های تصادفی) در یک الگوریتم احتمالی منجر به یک الگوریتم قطعی کارآمد برای همان مسئله می شود.

سودان گفت که کاغذ به دانشمندان رایانه کمک کرد تا درجاتی از تصادفی بودن را تشخیص دهند که می تواند به آشکار کردن پیچیدگی های مشکلات سخت و چگونگی حل آنها کمک کند. او گفت: "این فقط تصادفی نیست، بلکه تصورات تصادفی است." "این کلید است."

سودان اشاره می کند که به نظر می رسد تصادفی در همه جا ظاهر می شود، اما در حقیقت، یافتن آن بسیار سخت است. او گفت: «مردم به شما می گویند که ارقام pi تصادفی به نظر می رسند، یا دنباله اعدادی که اول هستند تصادفی به نظر می رسند. آنها کاملا مصمم هستند، اما برای ما تصادفی به نظر می رسند. او گفت که تصور تصادفی بودن در قلب علم کامپیوتر امروز نهفته است. "و این چیزی است که آوی به میزان زیادی تبلیغ کرده است."

تصادفی بودن به منبعی قدرتمند در نظریه پیچیدگی تبدیل شده است، اما گریزان است. ویگدرسون خاطرنشان می کند که چرخش سکه و تاس ریختن واقعاً تصادفی نیست: اگر اطلاعات کافی در مورد سیستم فیزیکی دارید، نتیجه کاملاً قابل پیش بینی است. او گفت که تصادفی بودن کامل، گریزان است و تأیید آن سخت است.

اما برای ویگرسون، نمونه‌هایی از محاسبات در همه جا وجود دارد - نه فقط در گوشی‌های هوشمند و لپ‌تاپ‌ها و الگوریتم‌های رمزگذاری، بلکه در سیستم‌های بیولوژیکی و فیزیکی نیز. در دهه‌های اخیر، یافته‌های تئوری محاسبات بینش‌هایی را در مورد طیف وسیعی از مشکلات غیرمنتظره، از ازدحام پرندگان و نتایج انتخابات گرفته تا واکنش‌های بیوشیمیایی در بدن به دست آورده‌اند. اساساً، هر فرآیند طبیعی یک تکامل است که شما می توانید آن را به عنوان محاسبات مشاهده کنید، بنابراین می توانید آن را به عنوان چنین مطالعه کنید. تقریباً همه چیز محاسبه می شود.»