چرا دانشمندان کامپیوتر با اوراکلها مشورت میکنند؟
از یک توپ جادویی 8 سوال بپرسید، و به شما بله، نه یا چیزی به طرز آزاردهندهای مردد پاسخ خواهد داد. ما آن را به عنوان اسباب بازی بچهها در نظر میگیریم، اما دانشمندان کامپیوتر نظری از ابزار مشابهی استفاده میکنند. آنها اغلب تصور میکنند که میتوانند با دستگاههای فرضی به نام اوراکل مشورت کنند که میتوانند فوراً و به درستی به سؤالات خاصی پاسخ دهند. این آزمایشهای فکری خیالی، الگوریتمهای جدیدی را الهام بخشیده و به محققان کمک کرده است تا نقشه محاسبات را ترسیم کنند.
محققانی که به اوراکلها متوسل میشوند، در زیرشاخهای از علوم کامپیوتر به نام نظریه پیچیدگی محاسباتی فعالیت میکنند. آنها به دشواری ذاتی مسائل مانند تعیین اینکه آیا یک عدد اول است یا یافتن کوتاهترین مسیر بین دو نقطه در یک شبکه، علاقهمند هستند. حل برخی از مسائل آسان است، به نظر میرسد حل برخی دیگر بسیار دشوارتر باشد اما راه حلهایی دارند که بررسی آنها آسان است، در حالی که برخی دیگر برای رایانههای کوانتومی آسان هستند، اما ظاهراً برای رایانههای معمولی دشوار هستند.
نظریهپردازان پیچیدگی میخواهند بفهمند که آیا این تفاوتهای ظاهری در دشواری اساسی هستند یا خیر. آیا چیز ذاتی در مورد برخی از مسائل وجود دارد که حل آنها را دشوار میکند، یا اینکه ما به اندازه کافی باهوش نیستیم که راه حل خوبی ارائه دهیم؟ محققان با دستهبندی مسائل در " دستههای پیچیدگی" به چنین سوالاتی پاسخ میدهند - برای مثال، همه مسائل آسان در یک دسته قرار میگیرند، و همه مسائل با بررسی آسان در دسته دیگری قرار میگیرند - و قضایایی را در مورد روابط بین آن دستهها ثابت میکنند.
متاسفانه، نقشهبرداری از چشمانداز دشواری محاسباتی، خوب، دشوار بوده است. بنابراین در اواسط دهه 1970، برخی از محققان شروع به مطالعه کردند که اگر قوانین محاسبات متفاوت بود، چه اتفاقی میافتاد. اینجاست که اوراکلها وارد میشوند.
اوراکلها مانند توپهای جادویی 8، دستگاههایی هستند که بلافاصله به سوالات بله یا خیر پاسخ میدهند، بدون اینکه چیزی در مورد عملکرد داخلی خود فاش کنند. برخلاف توپهای جادویی 8، آنها همیشه یا بله یا نه میگویند و همیشه درست هستند - یک مزیت خیالی بودن. علاوه بر این، هر اوراکل معین فقط به نوع خاصی از سوال مانند "آیا این عدد اول است؟" پاسخ میدهد.
چه چیزی این دستگاههای خیالی را برای درک دنیای واقعی مفید میکند؟ به طور خلاصه، آنها میتوانند ارتباطات پنهانی بین دستههای پیچیدگی مختلف را آشکار کنند.
دو دسته پیچیدگی معروف را در نظر بگیرید. دسته ای از مسائل وجود دارد که حل آنها آسان است، که محققان آن را "P" مینامند، و دستهای از مسائل که بررسی آنها آسان است، که محققان آن را "NP" مینامند. آیا تمام مسائل با بررسی آسان، حل آسانی هم دارند؟ اگر چنین باشد، این بدان معناست که NP برابر با P خواهد بود، و تمام رمزگذاری ها به راحتی قابل شکستن خواهند بود (در میان سایر پیامدها). نظریهپردازان پیچیدگی مشکوک هستند که NP برابر با P نیست، اما نمیتوانند آن را ثابت کنند، حتی اگر بیش از 50 سال است که تلاش میکنند رابطه بین این دو کلاس را مشخص کنند.
اوراکلها به آنها کمک کردهاند تا درک بهتری از آنچه که با آن کار میکنند، داشته باشند. محققان اوراکلهایی را اختراع کردهاند که به سوالاتی پاسخ میدهند که به حل بسیاری از مسائل مختلف کمک میکند. در دنیایی که هر رایانه خط مستقیمی با یکی از این اوراکلها داشت، تمام مسائل با بررسی آسان نیز آسان برای حل بودند و P برابر با NP میشد. اما اوراکلهای دیگر و کمتر مفید اثر متضادی دارند. در دنیایی که این اوراکلها در آن وجود دارند، P و NP به طور قابل اثباتی متفاوت خواهند بود.
محققان از این دانش برای درک بهتر مسئله P در مقابل NP استفاده کردهاند. اولین تلاشها برای تعیین رابطه بین P و NP از یک ترفند ظریف به نام قطری سازی استفاده کردند که برای سایر نتایج عمده در علوم کامپیوتر ضروری بود. اما محققان به زودی متوجه شدند که هر اثباتی مبتنی بر قطری سازی، در هر دنیایی که هر رایانه بتواند با همان اوراکل مشورت کند، نیز اعمال خواهد شد. این به معنای نابودی بود، زیرا اوراکلها پاسخ به سوال P در مقابل NP را تغییر میدهند. اگر محققان میتوانستند از قطری سازی برای اثبات این که P و NP در دنیای واقعی متفاوت هستند، استفاده کنند، همان اثبات به این معنی بود که P و NP در دنیای آغشته به اوراکل که در آن به وضوح معادل هستند، متفاوت هستند. این بدان معناست که هر راه حل مبتنی بر قطری سازی برای مسئله P در مقابل NP، خود متناقض خواهد بود. محققان نتیجه گرفتند که برای پیشرفت به تکنیکهای جدیدی نیاز دارند.
اوراکلها در مطالعه محاسبات کوانتومی نیز مفید بودهاند. در دهههای 1980 و 1990، محققان راههایی را برای استفاده از فیزیک کوانتومی کشف کردند تا به سرعت مسائل خاصی را حل کنند که به نظر میرسید برای رایانههای "کلاسیک" معمولی دشوار است. اما آیا این مسائل فقط سخت به نظر میرسیدند یا واقعاً سخت بودند؟ اثبات آن به هر طریقی نیازمند تکنیکهای ریاضی کاملاً جدیدی بود.
به همین دلیل، محققان بررسی کردهاند که رایانههای کوانتومی چگونه در مسائل مربوط به اوراکلها عمل میکنند. این تلاشها میتوانند شواهد غیرمستقیم ارائه دهند که رایانههای کوانتومی واقعاً قدرتمندتر از رایانههای کلاسیک هستند، و میتوانند به محققان در کشف وظایف جدید کیفی که در آن رایانههای کوانتومی ممکن است برتری داشته باشند، کمک کنند. گاهی اوقات، آنها حتی میتوانند کاربردهای عملی داشته باشند. در سال 1994، پیتر شور، ریاضیدان کاربردی، با الهام از نتیجه اخیر اوراکل، یک الگوریتم کوانتومی سریع برای تجزیه اعداد بزرگ ایجاد کرد - وظیفهای که دشواری ظاهری آن زیربنای سیستمهای رمزنگاری است که از دادههای آنلاین ما محافظت میکند. کشف شور، رقابتی را برای ساخت رایانههای کوانتومی قدرتمند آغاز کرد که تا به امروز ادامه دارد.
پیشبینی آینده نظریه پیچیدگی دشوار است، اما پاسخ دادن به هر سوالی در مورد مسیر این رشته به یک اندازه دشوار نیست. آیا محققان به مشورت با اوراکلها ادامه خواهند داد؟ نشانهها حاکی از بله است.