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

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

به یاد می آورد: «این باعث شد بنشینم و توجه کنم کارموسینو، اکنون یک دانشمند نظری کامپیوتر در IBM است. او برای یک سمینار اختیاری در مورد کار کورت گودل ثبت نام کرد، که استدلال‌های خودارجاعی سرگیجه‌آور او ابتدا محدودیت‌های استدلال ریاضی را آشکار کرد و پایه‌ای را برای تمام کارهای آینده در مورد محدودیت‌های اساسی محاسبات ایجاد کرد. قبول کردنش زیاد بود

کارموسینو گفت: "100% متوجه نشدم." "اما من می دانستم که می خواهم."

امروزه، حتی محققان باتجربه در مواجهه با پرسش باز محوری در علم کامپیوتر نظری، که به عنوان مسئله P در مقابل NP شناخته می‌شود، درک کمی پیدا می‌کنند. در اصل، این سؤال می‌پرسد که آیا بسیاری از مسائل محاسباتی که مدت‌ها بسیار دشوار تلقی می‌شوند، واقعاً می‌توانند به راحتی حل شوند (از طریق میانبر مخفی که هنوز کشف نکرده‌ایم)، یا همانطور که اکثر محققان گمان می‌کنند، واقعاً سخت هستند. در خطر چیزی کمتر از ماهیت چیزهای قابل شناخت نیست.

علیرغم دهه ها تلاش محققان در زمینه نظریه پیچیدگی محاسباتی - مطالعه چنین سؤالاتی در مورد دشواری ذاتی مسائل مختلف - راه حلی برای سؤال P در مقابل NP مبهم باقی مانده است. و حتی مشخص نیست که اثبات احتمالی از کجا باید شروع شود.

گفت: "هیچ نقشه راهی وجود ندارد." مایکل سیپسر، یک نظریه پرداز کهنه کار پیچیدگی در موسسه فناوری ماساچوست که سال ها در دهه 1980 با این مشکل دست و پنجه نرم می کرد. "مثل اینکه داری به بیابان می روی."

به نظر می رسد که اثبات اینکه حل مسائل محاسباتی سخت است، خود کار سختی است. اما چرا اینقدر سخت است؟ و چقدر سخت است؟ کارموسینو و سایر محققین در حوزه فرعی فراپیچیدگی، سؤالاتی از این قبیل را به عنوان مسائل محاسباتی مجدداً فرموله می کنند و با برگرداندن لنز نظریه پیچیدگی به سمت خود، زمینه را به جلو می برند.

"شاید فکر کنید، "خوب، این خیلی جالب است. شاید نظریه پردازان پیچیدگی دیوانه شده باشند راهول ایلانگو، یک دانشجوی کارشناسی ارشد در MIT که برخی از هیجان انگیزترین نتایج اخیر را در این زمینه به دست آورده است.

با مطالعه این پرسش‌های درون‌نگر، محققان دریافته‌اند که سختی اثبات سختی محاسباتی به سؤالات اساسی مرتبط است که ممکن است در ابتدا نامرتبط به نظر برسند. تشخیص الگوهای پنهان در داده های ظاهرا تصادفی چقدر سخت است؟ و اگر مشکلات واقعاً سختی وجود داشته باشد، چند وقت یکبار سخت هستند؟

او گفت: «روشن شده است که فراپیچیدگی به قلب همه چیز نزدیک است اسکات آرونسون، نظریه پرداز پیچیدگی در دانشگاه تگزاس، آستین.

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

ناشناخته های شناخته شده

مسئله P در مقابل NP نام کم رنگ خود را مدیون عادت نظریه پردازان پیچیدگی در مرتب کردن مسائل محاسباتی به کل است.کلاس های پیچیدگی” با برچسب هایی که نشان دهنده نمادهای نزدک هستند. یک مسئله محاسباتی مسئله ای است که در اصل می تواند توسط یک الگوریتم حل شود - یک لیست دقیقاً مشخص از دستورالعمل ها. اما همه الگوریتم‌ها به یک اندازه مفید نیستند، و تنوع بین الگوریتم‌ها به تفاوت‌های اساسی بین مسائل در کلاس‌های مختلف اشاره دارد. چالش نظریه پردازان پیچیدگی تبدیل این نکات به قضایای دقیق در مورد روابط بین طبقات پیچیدگی است.

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

"P" و "NP" دو عضو مشهور a هستند پرورشگاه در حال رشد از صدها کلاس پیچیدگی به طور کلی، P کلاسی از مسائلی است که می توان آنها را به راحتی حل کرد، مانند حروف الفبا کردن یک لیست. NP دسته ای از مسائل با راه حل های به راحتی قابل بررسی است، مانند پازل سودوکو. از آنجایی که بررسی همه مسائل به راحتی قابل حل نیز آسان است، مسائل در P نیز در NP هستند. اما حل برخی از مشکلات NP سخت به نظر می رسد - شما نمی توانید بلافاصله راه حل یک پازل سودوکو را بدون امتحان کردن بسیاری از احتمالات بشناسید. آیا ممکن است این سختی ظاهری فقط یک توهم باشد - اینکه یک ترفند ساده برای حل هر مشکلی که به راحتی قابل بررسی است وجود دارد؟

اگر چنین است، پس P = NP: دو کلاس معادل هستند. اگر چنین است، باید الگوریتمی وجود داشته باشد که حل پازل های سودوکو عظیم، بهینه سازی مسیرهای حمل و نقل جهانی، شکستن رمزگذاری پیشرفته و خودکار کردن اثبات قضایای ریاضی را بی اهمیت می کند. اگر P ≠ NP باشد، بسیاری از مسائل محاسباتی که در اصل قابل حل هستند، در عمل برای همیشه فراتر از درک ما باقی خواهند ماند.

محققان در مورد محدودیت های استدلال رسمی ریاضی مدت ها قبل از بیان مسئله P در مقابل NP نگران بودند - در واقع، مدت ها قبل از شروع علم کامپیوتر مدرن. در سال 1921، دیوید هیلبرت، ریاضیدان، با همان سؤالی که تقریباً یک قرن بعد توجه کارموسینو را به خود جلب کرد، یک برنامه تحقیقاتی برای پایه گذاری ریاضیات با قطعیت مطلق پیشنهاد کرد. او امیدوار بود که از چند فرض ساده به نام بدیهیات شروع کند و یک نظریه ریاضی یکپارچه را استخراج کند که سه معیار کلیدی را برآورده کند.

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

تنها یک سال بعد، گودل اولین ضربه را به رویای هیلبرت وارد کرد. او ثابت که یک گزاره خودباختگی مانند "این جمله غیر قابل اثبات است" را می توان از هر مجموعه بدیهیات مناسبی استخراج کرد. اگر چنین گزاره‌ای واقعاً غیرقابل اثبات باشد، نظریه ناقص است، اما اگر قابل اثبات باشد، نظریه ناسازگار است - نتیجه‌ای حتی بدتر. در همان مقاله، گودل همچنین ثابت کرد که هیچ نظریه ریاضی هرگز نمی تواند سازگاری خود را ثابت کند.

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

سپس در سال 1936، یک دانشجوی 23 ساله فارغ التحصیل به نام آلن تورینگ شرایط تصمیم پذیری هیلبرت را به زبان محاسباتی ناآشنا در آن زمان بیان کرد و ضربه مهلکی به آن وارد کرد. تورینگ یک مدل ریاضی را فرموله کرد - که اکنون به آن معروف است دستگاه تورینگ - که می تواند همه الگوریتم های ممکن را نشان دهد و نشان داد که اگر رویه هیلبرت وجود داشته باشد، در این مدل قرار می گیرد. او سپس از روش های خود ارجاعی مانند روش گودل استفاده کرد ثابت وجود عبارات غیرقابل تصمیم - یا به طور معادل، مسائل غیرقابل محاسبه که هیچ الگوریتمی قادر به حل آنها نیست.

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

در دهه 1960، دانشمندان کامپیوتر الگوریتم‌های سریعی را برای حل برخی مسائل توسعه دادند، در حالی که برای برخی دیگر، تنها الگوریتم‌های شناخته‌شده به‌شدت کند بودند. اگر سوال فقط این نبود که آیا مشکلات قابل حل هستند، بلکه حل آنها چقدر سخت است؟

کارموسینو گفت: «یک نظریه غنی پدیدار می‌شود و ما دیگر پاسخ‌ها را نمی‌دانیم.

مسیرهای واگرا

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

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

الگوریتم‌های مسیر همیلتونی پیچیده‌تری وجود دارند که مبارزه بهتری را ارائه می‌کنند، اما زمانی که الگوریتم‌ها برای حل مشکل نیاز دارند، همواره با اندازه نمودار به طور تصاعدی افزایش می‌یابد. قبل از اینکه بهترین الگوریتم‌هایی که محققین کشف کرده‌اند نتوانند مسیری را «در هر زمان معقولی» پیدا کنند، لازم نیست نمودارها خیلی بزرگ باشند. راسل ایمپاگلیازو، نظریه پرداز پیچیدگی در دانشگاه کالیفرنیا، سن دیگو. "و منظور من از "مدت زمان معقول" "قبل از پایان جهان است."

مسئله مسیر همیلتونی ویژگی جالب دیگری دارد. اگر کسی ادعا می کند که یک مسیر همیلتونی را در یک گراف خاص پیدا کرده است، می توانید به سرعت بررسی کنید که آیا راه حل معتبر است، حتی اگر نمودار بسیار بزرگ باشد. تنها کاری که باید انجام دهید این است که مسیر را دنبال کنید و گره ها را یکی یکی علامت بزنید و بررسی کنید که هیچ گره ای را دو بار تیک نخورده اید. اگر هیچ گره ای در انتها وجود نداشته باشد، مسیر همیلتونی است.

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

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

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

هم مسئله مسیر همیلتونی و هم مسئله مسیر اویلر در کلاس پیچیدگی NP هستند که به گونه ای تعریف شده است که شامل تمام مسائلی است که راه حل های آنها را می توان با الگوریتم های چند جمله ای بررسی کرد. مسئله مسیر اویلری نیز در کلاس P قرار می گیرد، زیرا یک الگوریتم چند جمله ای می تواند آن را حل کند، اما از نظر ظاهری، این برای مسئله مسیر همیلتونی صادق نیست. چرا باید این دو مشکل نمودار، که از نظر ظاهری به هم شباهت دارند، اینقدر تفاوت چشمگیری داشته باشند؟ این ماهیت مسئله P در مقابل NP است.

جهانی سخت

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

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

کوک مشکوک بود که هیچ الگوریتم سریعی برای مشکل جهانی او وجود ندارد، و در اواسط مقاله گفت: "من احساس می کنم ارزش تلاش قابل توجهی برای اثبات این حدس را دارد." "تلاش قابل توجه" به نظر می رسد دست کم گرفته شود.

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

این به معنای تمام مشکلات NP-complete - مسئله مسیر همیلتونی، سودوکو و هزاران نفر از دیگران - به معنای دقیق معادل هستند. ایلانگو گفت: "شما همه این وظایف طبیعی مختلف را دارید، و همه آنها به طرز جادویی یک وظیفه هستند." و ما هنوز نمی دانیم که آیا همان کار امکان پذیر است یا نه.

حل مشکل هر مشکل NP-complete برای حل سوال P در مقابل NP کافی است. اگر P ≠ NP، تمایز بین مسائل آسان و سخت توسط هزاران ستون که همه به یک اندازه قوی هستند حفظ می شود. اگر P = NP، کل ساختمان در آستانه فروپاشی است، فقط منتظر سقوط یک قطعه است.

کوک، لوین و کارپ مشکلاتی را که به نظر بسیاری از مشکلات نامربوط به نظر می رسید، متحد کرده بودند. اکنون تنها کاری که نظریه پردازان پیچیدگی باید انجام می دادند این بود که یک مسئله را حل کنند: آیا P = NP است یا نه؟

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

فرض کنید که P = NP. برای اثبات آن، محققان باید یک الگوریتم سریع برای یک مسئله NP-complete پیدا کنند، که ممکن است در گوشه ای مبهم از آن چشم انداز وسیع پنهان شده باشد. هیچ تضمینی وجود ندارد که آنها به زودی آن را پیدا کنند: نظریه پردازان پیچیدگی گاهی اوقات چنین کرده اند کشف الگوریتم‌های مبتکرانه برای مشکلات به ظاهر سخت (اگرچه نه NP-کامل) تنها پس از چندین دهه کار.

حال فرض کنید که P ≠ NP. اثبات آن حتی سخت تر به نظر می رسد. نظریه‌پردازان پیچیدگی باید ثابت کنند که هیچ الگوریتم سریعی نمی‌تواند وجود داشته باشد، که به طور موثر بهترین تلاش‌های همه محققان آینده را پیش‌بینی و خنثی کند.

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

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

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

کارموسینو می‌گوید: «می‌دانی، اگر می‌خواهی این کار را ادامه بدهی، اگر می‌خواهی علوم کامپیوتر نظری و تئوری پیچیدگی را ادامه بدهی، می‌توانی: به این مدرسه فارغ‌التحصیل می‌گویند.» پس از اخذ مدرک کارشناسی ارشد، در سال 2012 به سن دیگو نقل مکان کرد تا در مقطع دکترا تحت نظارت ایمپاگلیازو کار کند.

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

این "موانع اثبات طبیعی" تنها یکی از بسیاری از موانع شناخته شده برای حل مسائل باز در نظریه پیچیدگی است. هر کدام مانند یک سد عمل می کنند و هشدار می دهند که یک مسیر به ظاهر امیدوارکننده در واقع یک بن بست است. این موانع با هم نشان می‌دهند که هر مدرکی که مشکل P در مقابل NP را حل می‌کند باید کاملاً متفاوت از هر چیزی باشد که در گذشته استفاده شده است. به همین دلیل است که اکثر محققان بر این باورند که راه حل بسیار دور باقی مانده است. اما حداقل موانع به آنها می گوید که کجا را نگاه نکنند.

ایلانگو گفت: «تئوری پیچیدگی هم نفرین شده است و هم دارای موانع بسیار زیادی است.

زمانی که Carmosino با سد اثبات طبیعی روبرو شد، تقریباً 20 سال از عمر آن گذشته بود. اما او مشکوک بود که درس های بیشتری برای محققان داشته باشد. این احساس روزی زمانی که او و سه همکارش با بررسی مانع اثبات طبیعی از منظر فراپیچیدگی، نتیجه شگفت‌آوری را به اثبات رساندند. اثبات آنها یکی از معدود نتایج مهمی بود که باعث ایجاد علاقه جدیدی به فراپیچیدگی شد و منجر به انبوهی از پیشرفت ها در چندین سال گذشته شد.

اما برای دنبال کردن مسیری از مانع اثبات طبیعی تا فراپیچیدگی، باید به جایی برگردیم که محققان را در دهه 1970 ترک کردیم، زمانی که آنها برای اولین بار شروع به مقابله با مسئله P در مقابل NP کردند. چه چیزی اثبات مشکلات را سخت کرده است؟

یک مسیر مداری

در ابتدا، محققان سعی کردند P ≠ NP را ثابت کنند - یعنی ثابت کنند که برخی از مسائل NP با هیچ الگوریتم چند جمله ای ممکن قابل حل نیستند - با استفاده از تغییراتی در تکنیک هایی که تورینگ برای اثبات اینکه برخی از مسائل با هیچ الگوریتمی قابل حل نیستند استفاده کرده است. . اما آنها به سرعت کشف دلیلی بر این که آن روش ها کار نمی کنند - اولین مانع اصلی برای حل مسئله P در مقابل NP. بنابراین آنها شروع به جستجوی رویکرد دیگری کردند و به زودی یکی از آنها را در آثار معاصر تورینگ یافتند کلود شانون.

شانون، که در شهر کوچکی در شمال میشیگان بزرگ شد، برای آغاز عصر اطلاعات، شخصیتی بعید به نظر می رسید. با این حال، او ماهیت میان رشته‌ای رشته نوظهور علوم کامپیوتر را مثال زد و در مهندسی برق و منطق ریاضی به همان اندازه احساس راحتی کرد. در او پایاننامهی کارشناسی ارشدشانون نشان داد که چگونه مدارهای ساخته شده از سوئیچ های الکترومکانیکی می توانند عبارات منطقی شامل متغیرهای بولی را نشان دهند - کمیت هایی که فقط می توانند دو مقدار (مانند true یا false یا 1 و 0) بگیرند.

در این عبارات، متغیرهای بولی توسط "دروازه های منطقی" AND، OR و NOT به یکدیگر مرتبط می شوند. برای مثال، عبارت ابتدایی A و B زمانی درست است که A و B هر دو درست و در غیر این صورت نادرست باشند. از طرف دیگر، A OR B در صورتی صادق است که حداقل یکی از دو متغیر درست باشد. یک دروازه NOT ساده تر است: مقدار یک متغیر را معکوس می کند. با داشتن تعداد کافی از این بلوک های ساختمانی اساسی، می توانید هر محاسباتی را انجام دهید.

وقتی به رایانه خود نگاه می کنید، در پایان روز، چه کار می کند؟ ایلانگو گفت.

کار شانون راه جدیدی را برای نظریه پردازان پیشنهاد کرد تا در مورد دشواری مسائل محاسباتی فکر کنند، به نام «پیچیدگی مدار»، حتی اگر مدارهای مورد بحث فقط انتزاعات ریاضی هستند. برای مدتی، محققان فکر می‌کردند که این رویکرد می‌تواند راهی برای حل P در مقابل NP باشد، اما در نهایت این مسیر در برابر مانع اثبات طبیعی قرار گرفت.

چارچوب پیچیدگی مدار مستلزم بازنگری در اساسی ترین مفاهیم در مدل محاسبات تورینگ است. در اینجا، محققان به جای مسائل محاسباتی و الگوریتم هایی که آنها را حل می کنند، توابع بولی و مدارهایی که آنها را محاسبه می کنند، در نظر می گیرند. یک تابع بولی متغیرهای بولی - درست و غلط، 1 و 0 - را می گیرد و درست یا نادرست، 1 یا 0 را خروجی می دهد. و مانند یک الگوریتم، یک مدار رویه ای را برای تولید خروجی با هر ورودی توصیف می کند.

گفت: "درک من این است که مردم شروع به کار بر روی پیچیدگی مدار کردند زیرا به این نتیجه رسیدند که ماشین های تورینگ بسیار پیچیده هستند." رایان ویلیامز، یک نظریه پرداز پیچیدگی در MIT. "ما می توانیم مدارها را دروازه به دروازه مطالعه کنیم."

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

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

یک تابع بولی آسان برای محاسبه شبیه به یک مسئله محاسباتی در کلاس P است - یکی که می تواند با الگوریتمی حل شود که در زمان چند جمله ای اجرا می شود. اما توابعی مشابه مسائل سخت NP نیز وجود دارد، که در آن بهترین روشی که محققان برای محاسبه نسخه‌های بزرگ‌تر کشف کرده‌اند، نیازمند افزایش تصاعدی تعداد گیت‌ها است، اما پاسخ به راحتی قابل بررسی است. اگر نظریه‌پردازان پیچیدگی بتوانند ثابت کنند که واقعاً هیچ راه بهتری برای محاسبه چنین تابعی وجود ندارد، این به معنای P ≠ NP است.

این راهبردی بود که اکثر نظریه پردازان پیچیدگی در دهه 1980 دنبال کردند. و شانس با آنها بود. شانون داشت ثابت در سال 1949 تقریباً هر جدول صدق بولی (که فقط یک لیست طولانی از همه ورودی ها و خروجی های ممکن یک تابع بولی با اندازه ثابت است) دارای پیچیدگی مدار است که عملاً تا حد امکان بالا است. او از یک استدلال ساده و خیره کننده استفاده کرد: روش های بسیار کمتری برای ترکیب تعداد کمی از دروازه ها نسبت به راه های ترکیب بسیاری از دروازه ها وجود دارد.

آرونسون گفت: «مدارهای کوچک کافی برای دور زدن وجود ندارد.

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

Crypto Bros

در ابتدا پیشرفت سریع بود. در سال 1981، Sipser و دو همکار ثابت اگر از مدارهایی با محدودیت‌های خاصی در مورد نحوه چیدمان گیت‌ها استفاده می‌کردند، محاسبه یک تابع بولی مشخص قطعاً سخت بود.

Sipser گفت: "فانتزی این بود که شما بتوانید چیزهایی را در مورد این مدل های محدود ثابت کنید، و سپس بر اساس آنچه آموخته اید با محدودیت های کمتر و کمتر کار کنید."

رازبروف در سال 1985 قدم بزرگ بعدی را برداشت. او به تازگی تحصیلات تکمیلی را در مسکو شروع کرده بود و به طور تصادفی به این تلاش پیوسته بود، در حالی که به یک مسئله در شاخه دیگری از ریاضیات پرداخته بود، جایی که معلوم شد که حل مسئله P در مقابل NP یک پیش نیاز است.

رازبروف گفت: "من خیلی خوش شانس بودم که نمی دانستم این مشکل چقدر سخت است." "وگرنه شاید حتی شروع نمی کردم."

رازبروف مدارهایی را که فقط حاوی گیت‌های AND و OR بودند و ثابت محاسبه یک تابع خاص با استفاده از چنین مدارهایی، مهم نیست که دروازه‌ها چگونه چیده شده‌اند، دشوار است - علاوه بر این، آن تابع به‌عنوان NP-complete شناخته می‌شود. تمام کاری که محققان برای حل P در مقابل NP باید انجام می دادند، گسترش تکنیک های Razborov به مدارهایی با دروازه های NOT بود.

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

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

ایمپاگلیازو گفت: «شوخی ما این بود که می‌خواستیم دکمه‌ای بگیریم که روی آن «ارجاع به خود» نوشته شده بود.

به عنوان دانشجویان فارغ التحصیل، رودیچ و ایمپاگلیازو روی مبانی نظری پیچیدگی رمزنگاری کار کردند، موضوعی که شاید بهترین انگیزه عملی را برای تلاش برای اثبات P ≠ NP ارائه می دهد. رمزنگاران پیام های مخفی را با پوشاندن آنها به صورت "شبه تصادفی" پنهان می کنند - پیامی که به این روش رمزگذاری شده است برای هر استراق سمع کننده ای مانند یک ترکیب تصادفی از اعداد به نظر می رسد، اما همچنان می تواند توسط گیرنده مورد نظر رمزگشایی شود. اما چگونه می توان مطمئن بود که یک استراق سمع برای شکستن کد بسیار مشکل خواهد بود؟

اینجاست که تئوری پیچیدگی وارد می‌شود. روش‌های رمزگذاری که امروزه به طور گسترده مورد استفاده قرار می‌گیرند، همگی مبتنی بر مشکلات به ظاهر سخت NP هستند - برای رمزگشایی پیام، یک مهاجم برای حل مشکل به یک الگوریتم سریع هنوز کشف نشده نیاز دارد. برای اثبات اینکه این روش ها واقعا ایمن هستند، یک کاری که باید انجام دهید این است که ثابت کنید P ≠ NP. سیپسر گفت، بدون اثبات، تنها کاری که می‌توانید انجام دهید این است که «امیدوار باشید هر کسی که می‌خواهید راز را از او پنهان کنید، ریاضیدان بهتری از شما نباشد».

اگرچه رمزنگاری در نوع خود جذاب بود، اما به نظر می‌رسید که رمزنگاری از استدلال‌های خودارجاعی که ابتدا رودیچ و ایمپاگلیازو را به این حوزه کشانده بودند، فاصله زیادی داشته باشد. اما زمانی که رودیچ در تلاش بود تا بفهمد چرا رویکرد پیچیدگی مدار متوقف شده است، متوجه شد که در نهایت این دو موضوع چندان از هم دور نیستند. راهبردی که محققان در تلاش‌های خود برای اثبات اینکه P ≠ NP اتخاذ کرده بودند، شخصیتی خودباختگی دارد که یادآور گزاره معروف گودل «این جمله غیرقابل اثبات است» است - و رمزنگاری می‌تواند به توضیح دلیل آن کمک کند. در روسیه، رازبوروف در همان زمان یک ارتباط مشابه را کشف کرد. اینها بذرهای مانع اثبات طبیعی بودند.

تنش در قلب مانع اثبات طبیعی این است که وظیفه تشخیص توابع با پیچیدگی بالا از توابع کم پیچیدگی شبیه به کار تشخیص تصادفی واقعی از شبه تصادفی مورد استفاده برای رمزگذاری پیام ها است. برای اثبات P ≠ NP می خواهیم نشان دهیم که توابع با پیچیدگی بالا به طور کلی با توابع کم پیچیدگی متفاوت هستند. اما ما همچنین دوست داریم که تصادفی بودن کاذب از تصادفی بودن قابل تشخیص نباشد، تا از امنیت رمزنگاری اطمینان داشته باشیم. شاید ما نتوانیم از هر دو طرف آن را داشته باشیم.

یک شوخی بی رحمانه

در سال 1994، رازبوروف و رودیچ متوجه شدند که به بینش های مشابهی دست یافته اند و شروع به کار با یکدیگر برای ترکیب نتایج خود کردند. آنها ابتدا مشاهده کردند که تمام تلاش‌های قبلی برای اثبات P ≠ NP با استفاده از پیچیدگی مدار، همان استراتژی کلی را اتخاذ کرده بودند: یک ویژگی خاص از یک تابع بولی NP-complete را شناسایی کنید، سپس ثابت کنید که هیچ تابع آسان برای محاسبه نمی‌تواند آن ویژگی را به اشتراک بگذارد. این نشان می‌دهد که محاسبه تابع NP-complete انتخاب شده واقعاً سخت است و P≠ NP را ثابت می‌کند.

Sipser، Razborov و دیگران از همین استراتژی برای اثبات نتایج محدودتر خود با موفقیت استفاده کرده بودند، و در هر مورد، ویژگی خاصی که محققان شناسایی کردند توسط اکثر توابع Boolean مشترک بود. رازبوروف و رودیچ اصطلاح "اثبات طبیعی" را برای اشاره به این مورد ابداع کردند که در آن اموال به طور گسترده به اشتراک گذاشته می شد، صرفاً به این دلیل که هیچ جایگزین شناخته شده ای وجود نداشت. اگر اثبات‌های «غیر طبیعی» امکان‌پذیر بود، باید بسیار غیرمعمول و مستحق این نام بودند.

رازبوروف و رودیچ نتیجه اصلی خود را ثابت کردند: اثبات طبیعی P ≠ NP مستلزم درک بسیار جامعی از تفاوت توابع آسان برای محاسبه و محاسبه سخت است و این دانش همچنین می تواند الگوریتم سریعی را برای تشخیص آسان ایجاد کند. -برای محاسبه توابع حتی اگر به طور سطحی پیچیده باشند. اگر نظریه‌پردازان پیچیدگی در اثبات طبیعی P ≠ NP موفق می‌شدند، راهی تقریباً اشتباه برای نگاه کردن به جدول صدق دلخواه و تعیین اینکه آیا تابع مربوطه دارای پیچیدگی مدار بالا یا پایین است، کشف می‌کردند - نتیجه‌ای بسیار قوی‌تر و کلی‌تر از آنها برای اثبات تصمیم گرفته بودند.

کارموسینو گفت: «تقریباً نمی‌توانید بیشتر از چیزی که برایش چانه‌زنی کرده‌اید به دست آورید.

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

برای درک این ارتباط، تصور کنید به ستون خروجی در جدول صدق یک تابع بولی با متغیرهای ورودی زیادی نگاه کنید و هر "درست" را با 1 و هر "نادرست" را با 0 جایگزین کنید:

اگر تابع بولی پیچیدگی مدار بالایی داشته باشد، آن لیست طولانی خروجی در اصل از یک رشته واقعا تصادفی 0 و 1 قابل تشخیص نخواهد بود - مثلاً رشته ای که با چرخاندن مکرر یک سکه به دست می آید. اما اگر تابع پیچیدگی مدار پایینی داشته باشد، رشته باید توصیفی ساده و مختصر داشته باشد، حتی اگر پیچیده به نظر برسد. این موضوع آن را بسیار شبیه به رشته های شبه تصادفی مورد استفاده در رمزنگاری می کند، که شرح مختصر آنها پیام مخفی مدفون در آن تصادفی ظاهری است.

بنابراین نتیجه رازبوروف و رودیچ نشان داد که هر اثبات طبیعی P ≠ NP همچنین الگوریتم سریعی به دست می‌دهد که می‌تواند رشته‌های شبه تصادفی حاوی پیام‌های پنهان را از رشته‌های واقعا تصادفی تشخیص دهد. رمزنگاری ایمن غیرممکن خواهد بود - دقیقاً برخلاف آنچه محققان امیدوار بودند با اثبات P ≠ NP ایجاد کنند.

از سوی دیگر، اگر رمزنگاری ایمن امکان پذیر باشد، اثبات طبیعی یک استراتژی قابل دوام برای اثبات P ≠ NP - پیش نیاز رمزنگاری ایمن نیست. به طور خلاصه این مانع اثبات طبیعی است. به نظر می رسید که نظریه پردازان پیچیدگی در حال دریافت یک شوخی بی رحمانه هستند.

کابانتس گفت: "اگر به سختی اعتقاد دارید، پس باید باور کنید که اثبات سختی سخت است."

به متاورس

این ارتباط بین مفاهیم حدس P ≠ NP و دشواری اثبات آن جالب بود، اما تعیین آن دشوار بود. برای یک چیز، مانع اثبات طبیعی تنها یک رویکرد برای اثبات P ≠ NP را مسدود کرد. برای دیگری، مشکل اثبات P ≠ NP را نه به خود P ≠ NP، بلکه به وجود رمزنگاری امن - مشکلی نزدیک اما نه کاملاً معادل، مرتبط می‌داند. برای درک واقعی این ارتباط، محققان باید با فراپیچیدگی راحت باشند.

ویلیامز گفت: "این شهود وجود دارد که "اوه، زیرا P ≠ NP، اثبات آن P ≠ NP دشوار است." اما برای اینکه حتی این شهود را درک کنید، باید در مورد اثبات چیزی مانند P ≠ NP به عنوان یک مشکل محاسباتی فکر کنید.

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

کابانتس به یاد می آورد: "من می خواستم کاری آکادمیک تر انجام دهم." و من هم کنجکاو بودم که دنیا را ببینم.» او برای تحصیلات تکمیلی به کانادا نقل مکان کرد و آنجا بود که با مانع اثبات طبیعی آشنا شد. مانند Carmosino، کابانتس با نتیجه شکست خورد. او گفت: «بسیار عمیق به نظر می رسید که شما این ارتباط را دارید.

در سال 2000، در اواخر دوران تحصیل در مقطع کارشناسی ارشد، او متوجه شد که مانع اثبات طبیعی در مکالماتش با جین یی کای، یک نظریه پرداز پیچیدگی که در آن زمان از تورنتو بازدید می کرد. آنها شروع کردند به این سد نه به عنوان یک مانع، بلکه به عنوان یک دعوت - فرصتی برای بررسی دقیق اینکه چقدر سخت است اثبات مشکلات. را مقاله که در آن آنها این دیدگاه جدید را ارائه کردند، به یکی از تأثیرگذارترین آثار اولیه در زمینه نوپای فراپیچیدگی تبدیل خواهد شد.

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

MCSP یک مسئله فراپیچیدگی اساسی است: یک مسئله محاسباتی که موضوع آن نظریه گراف یا موضوع خارجی دیگری نیست، بلکه خود نظریه پیچیدگی است. در واقع، این مانند یک نسخه کمی از این سؤال است که نظریه‌پردازان پیچیدگی را به مقابله با P در مقابل NP با استفاده از رویکرد پیچیدگی مدار در دهه 1980 سوق داد: محاسبه کدام توابع بولی دشوار است و کدام آسان است؟

ایمپاگلیازو گفت: «اگر ما به یک الگوریتم MCSP برسیم، این روشی است برای خودکارسازی کاری که در تئوری پیچیدگی انجام می‌دهیم. حداقل باید بینش فوق العاده ای در مورد اینکه چگونه کارمان را بهتر انجام دهیم به ما بدهد.

نظریه پردازان پیچیدگی نگران این نیستند که این الگوریتم جادویی آنها را از کار بیاندازد - آنها فکر نمی کنند که اصلاً وجود داشته باشد، زیرا رازبوروف و رودیچ نشان دادند که هر الگوریتمی از این قبیل برای تشخیص جداول حقیقت با پیچیدگی بالا از جدول های کم پیچیدگی باعث ایجاد رمزنگاری می شود. غیر ممکن این بدان معناست که MCSP احتمالاً یک مشکل محاسباتی سخت است. اما چقدر سخت است؟ آیا این NP-کامل است، مانند مسئله مسیر همیلتونی و تقریباً هر مشکل دیگری که محققان در دهه 1960 با آن دست و پنجه نرم کردند؟

برای مشکلات NP، "چقدر سخت است؟" معمولاً پاسخ دادن به اندازه کافی آسان است، اما به نظر می رسد MCSP یک چیز دور از ذهن است. کابانتس گفت: «ما مشکلات بسیار کمی «در اطراف» داریم که به این جزیره از مشکلات NP-کامل متصل نشده باشند، حتی اگر به نظر سخت باشند.

کابانتس می دانست که او و کای اولین کسانی نبودند که مشکلی را که MCSP نامیده بودند در نظر گرفتند. ریاضیدانان شوروی در آغاز دهه 1950، در تلاش اولیه برای درک دشواری ذاتی مسائل مختلف محاسباتی، مسئله ای بسیار مشابه را مطالعه کرده بودند. لئونید لوین در حالی که در اواخر دهه 1960 به نظریه NP-کامل بودن تبدیل می شد با آن دست و پنجه نرم می کرد، اما نتوانست آن را NP-complete ثابت کند و مقاله اصلی خود را بدون آن منتشر کرد.

پس از آن، این مشکل به مدت 30 سال توجه کمی را به خود جلب کرد، تا اینکه Kabanets و Cai به ارتباط آن با مانع اثبات طبیعی اشاره کردند. کابانتس انتظار نداشت خودش این سوال را حل کند - در عوض او می‌خواست بررسی کند که چرا اثبات این مشکل به ظاهر سخت در مورد سختی محاسباتی واقعاً سخت بوده است.

گفت: «این به یک معنا فراپیچیدگی است راهول سانتانام، نظریه پرداز پیچیدگی در دانشگاه آکسفورد.

اما آیا سختی آن تا آخر پایین آمد یا حداقل راهی برای فهمیدن اینکه چرا محققان در اثبات کامل بودن MCSP موفق نشده بودند وجود داشت؟ کابانتس کشف کرد که، بله، دلیلی وجود دارد: دشواری درک پیچیدگی مدار مانند مانعی برای هر استراتژی شناخته شده ای برای اثبات کامل بودن NP MCSP عمل می کند - مشکلی که خود مربوط به دشواری درک پیچیدگی مدار است. منطق پیچ خورده و خودشکسته سد اثبات طبیعی اجتناب ناپذیر به نظر می رسید.

همچنین ممکن است که MCSP NP-complete نباشد، اما این نیز بعید به نظر می‌رسد – برخی از انواع ساده‌تر مشکل از قبل به عنوان NP-complete شناخته شده‌اند.

ایمپاگلیازو گفت: «ما مکان خوبی برای قرار دادن آن نداریم که مستقیماً آن را با تمام مشکلات دیگری که مطالعه می کنیم مرتبط کند.

کابانتس رفتار عجیب MCSP را روشن کرده بود، اما او نمی دانست چگونه پیشرفت بیشتری کند. تحقیقات فراپیچیدگی تا حدی کاهش یافت. 16 سال بعد، زمانی که محققان یک ارتباط شگفت‌انگیز را با یک سوال اساسی دیگر کشف کردند، دوباره شکوفا شد: اگر بیشتر اوقات فقط به دریافت پاسخ صحیح اهمیت می‌دهید، حل مشکلات چقدر سخت است؟

جنگ های جهانی

برای مشکلات روزمره، پاسخ هایی که بیشتر اوقات جواب می دهند اغلب به اندازه کافی خوب هستند. ما رفت و آمدهایمان را برای الگوهای ترافیکی معمولی برنامه ریزی می کنیم، نه برای بدترین سناریوها.

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

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

در واقع این لوین بود که یک دهه پس از کار پیشگام خود در مورد کامل بودن NP، مطالعه دقیق پیچیدگی مورد متوسط ​​را آغاز کرد. در سال‌های میانی، او با مقامات شوروی برخورد کرد - او یک مزاحم بی‌احترام بود که گهگاه فعالیت‌های میهنی را در گروه جوانان حزب کمونیست خود تضعیف می‌کرد. در سال 1972 به دلایل صریحاً سیاسی از مدرک دکترا محروم شد.

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

لوین در سال 1978 به ایالات متحده مهاجرت کرد و در اواسط دهه 1980 توجه خود را به پیچیدگی پرونده متوسط ​​معطوف کرد. او شروع به همکاری با دیگران برای توسعه بیشتر این نظریه کرد، از جمله ایمپاگلیازو، دانشجوی کارشناسی ارشد در آن زمان. اما حتی زمانی که آنها پیشرفت کردند، ایمپاگلیازو متوجه شد که محققان اغلب از کنار یکدیگر صحبت می کنند. او می خواست همه را در یک صفحه قرار دهد، و این کمکی نکرد که مقالات لوین به طور معروف مختصر و مختصر بودند - همان چیزی که زمینه را آغاز کرد پیچیدگی متوسط ​​پرونده کمتر از دو صفحه بود.

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

La مقالهکه در سال 1995 منتشر شد، به یک کلاسیک فوری تبدیل شد. ایمپاگلیازو نام های عجیب و غریبی را برای آنها ابداع کرد پنج دنیا با درجات مختلف سختی محاسباتی و قابلیت‌های رمزنگاری متفاوت متمایز می‌شوند. ما در یکی از این دنیاها زندگی می کنیم، اما نمی دانیم کدام است.

از زمانی که مقاله ایمپاگلیازو ظاهر شد، محققان رویای حذف بخش‌هایی از چندجهانی مینیاتوری او را در سر می‌پرورانند - با ثابت کردن این که برخی از جهان‌ها در نهایت امکان‌پذیر نیستند، فضای احتمالات را محدود کنند. دو جهان به ویژه اهداف وسوسه انگیزی هستند: آنهایی که رمزنگاری غیرممکن است، حتی اگر P ≠ NP.

در یکی از این دنیاها که Heuristica نام دارد، همه مسائل NP-complete در اکثر ورودی‌ها به راحتی قابل حل هستند، اما الگوریتم‌های سریع گاهی اوقات اشتباه می‌کنند، بنابراین این مسائل هنوز با استانداردهای نظریه پیچیدگی بدترین حالت سخت در نظر گرفته می‌شوند. این دنیایی است که در آن رمزنگاری غیرممکن است زیرا تقریباً هر کدی به راحتی شکسته می شود. در دنیای دیگری که Pessiland نامیده می شود، رمزنگاری به دلیل دیگری غیرممکن است: هر مشکلی در حالت متوسط ​​دشوار است، اما رمزگذاری یک پیام آن را حتی برای گیرنده مورد نظر ناخوانا می کند.

معلوم شد که این دو جهان ارتباط تنگاتنگی با مشکلات فراپیچیدگی دارند - به ویژه، سرنوشت Heuristica با این سؤال طولانی مدت مرتبط است که آیا MCSP NP-کامل است یا خیر. سوالی که مدت ها پیش کابانتس را مجذوب خود کرد و لوین را به خود مشغول کرد، کنجکاوی محض نیست: یک دنیا در خطر است.

برای رد Heuristica، محققان باید تمایز بین پیچیدگی بدترین و متوسط ​​را از بین ببرند - یعنی باید ثابت کنند که هر الگوریتم فرضی که یک مسئله NP-complete را به درستی در اکثر ورودی ها حل کند، در واقع می تواند آن را حل کند. در تمام موارد این نوع ارتباط که کاهش بدترین حالت به متوسط ​​نامیده می‌شود، برای مشکلات خاصی وجود دارد، اما هیچ‌کدام از آنها NP-کامل نیستند، بنابراین این نتایج به هیچ چیز کلی تری دلالت نمی‌کنند. حذف Heuristica رمزنگاران را تا نیمه راه تحقق رویای رمزگذاری ایمن بر اساس این فرض واحد می برد که P ≠ NP.

اما نابود کردن یک دنیا کار کوچکی نیست. در سال 2003، دو نظریه پرداز پیچیدگی نشان داد این که رویکردهای موجود برای اثبات کاهش بدترین حالت تا متوسط ​​مورد برای مشکلات شناخته شده NP-complete پیامدهای عجیبی را به همراه خواهد داشت، که نشان می‌دهد احتمالاً چنین اثبات‌هایی ممکن نیست.

محققان باید رویکرد دیگری پیدا کنند و اکنون فکر می کنند MCSP ممکن است تنها مشکلی باشد که آنها نیاز دارند. اما این برای بیش از یک دهه روشن نشد. اولین نگاه اجمالی از ارتباط از شیفتگی مداوم مارکو کارموسینو به مانع اثبات طبیعی پدیدار شد.

کارموسینو برای اولین بار در دوران تحصیلات تکمیلی با تحقیقات فراپیچیدگی مواجه شد مقاله 2013 توسط Kabanets و چهار محقق دیگر، که رویکردی به مانع اثبات طبیعی را که Kabanets بیش از یک دهه قبل از آن پیشگام بود، توسعه دادند. این فقط اعتقاد او را تقویت کرد که هنوز چیزهای بیشتری برای یادگیری از مقاله کلاسیک رازبوروف و رودیچ وجود دارد.

کارموسینو می‌گوید: «در آن زمان وسواس زیادی نسبت به آن کاغذ داشتم. "هیچ چیز تغییر نکرده است."

این وسواس سرانجام در طی بازدید از کارگاه آموزشی یک ترم در دانشگاه کالیفرنیا، برکلی، به ثمر نشست، جایی که او بیشتر وقت خود را صرف صحبت با Impagliazzo، Kabanets و آنتونینا کولوکولووا، نظریه پرداز پیچیدگی در دانشگاه مموریال نیوفاندلند که با کابانتس در مقاله سال 2013 همکاری داشت. کارموسینو قبلاً یک بار با آن سه نفر کار کرده بود، و این همکاری موفق به او اعتماد به نفس داد تا آنها را با سؤالاتی در مورد موضوعی که بیش از همه او را مجذوب خود کرده بود، تقویت کند.

کابانتس به یاد می‌آورد: «او به طرز خوبی مردم را جست‌وجو می‌کرد.

در ابتدا، کارموسینو ایده های جدیدی برای اثبات کامل بودن NP برای نسخه MCSP داشت که در مقاله رازبوروف و رودیچ در مورد مانع اثبات طبیعی ظاهر شده بود. اما این ایده ها به نتیجه نرسیدند. درعوض، یک اظهارنظر خارج از کاف توسط Impagliazzo باعث شد چهار محقق متوجه شوند که مانع اثبات طبیعی می‌تواند الگوریتم‌های قوی‌تری از آنچه که هرکسی تصور می‌کرد به دست آورد - نقشه‌ای مخفی در این مانع حک شده بود.

در یک مقاله 2016چهار محقق ثابت کردند که نوع خاصی از الگوریتم MCSP با حالت متوسط ​​می‌تواند برای ساخت الگوریتم بدترین حالت برای شناسایی الگوهای پنهان در رشته‌های تصادفی اعداد استفاده شود - وظیفه‌ای که دانشمندان کامپیوتر از آن به عنوان "یادگیری" یاد می‌کنند. این یک نتیجه قابل توجه است زیرا یادگیری به طور شهودی سخت تر از کار طبقه بندی باینری - پیچیدگی بالا یا پیچیدگی کم - توسط یک الگوریتم MCSP به نظر می رسد. و در کمال تعجب، بدترین پیچیدگی یک کار را به پیچیدگی متوسط ​​مورد دیگر مرتبط کرد.

ایمپاگلیازو گفت: «معلوم نبود که چنین ارتباطی وجود داشته باشد.

یک الگوریتم سریع برای MCSP برای مدارهای بولی عمومی کاملاً فرضی است: این الگوریتم نمی‌تواند وجود داشته باشد مگر اینکه MCSP یک مشکل محاسباتی آسان باشد، با وجود همه شواهد برعکس، و این بدان معناست که الگوریتم یادگیری که توسط مقاله چهار محقق ذکر شده است. به همان اندازه فرضی

اما برای برخی از نسخه‌های ساده‌تر MCSP - تمایز جداول حقیقت با پیچیدگی بالا از جدول‌های پیچیدگی پایین در صورت وجود محدودیت‌های خاص در مدارها - الگوریتم‌های سریع سال‌هاست که شناخته شده‌اند. مقاله Carmosino، Impagliazzo، Kabanets و Kolokolova نشان داد که این الگوریتم‌ها را می‌توان به الگوریتم‌های یادگیری تبدیل کرد که به همین ترتیب محدود بودند، اما هنوز قدرتمندتر از الگوریتم‌هایی هستند که محققان قبلاً در چنین سطح نظری دقیقی درک کرده بودند.

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

نتیجه توجه نظریه پردازان پیچیدگی که روی موضوعات دیگر کار می کنند را به خود جلب کرد. همچنین پیش نمایشی از ارتباطات بیشتر بین فراپیچیدگی و پیچیدگی متوسط ​​موردی بود که در سال های آینده ظاهر می شد.

بیشتر از همه، این گواهی بود که محققان با پرسیدن سؤالات ساده در مورد موانعی که در ابتدا فقط مانع پیشرفت آنها می شوند، تا چه حد می توانند پیش بروند.

ایمپاگلیازو گفت: «این نوع دوگانگی موضوعی است که حداقل در 30 یا 40 سال گذشته از پیچیدگی گذشته است. "موانع اغلب فرصت ها هستند."

اعتباری جزئی

در سال‌هایی که کارموسینو و همکارانش مقاله‌شان را منتشر کردند، پیشرفت فقط سرعت گرفته است.

کولوکولووا گفت: «چیزهای جدیدی در حال رخ دادن است. "محققان جوان واقعاً بسیار باهوش بسیاری وجود دارد."

ایلانگو یکی از این محققان جوان است - در سه سال اول تحصیلات تکمیلی، او به مشکل باز و دلهره آور اثبات MCSP NP-complete با استفاده از یک استراتژی دو وجهی حمله کرد: اثبات کامل بودن NP برای ساده تر نسخه از MCSP، همانطور که محققان پیچیدگی مدار هنگام حمله به P در مقابل NP در دهه 1980 انجام دادند، در حالی که همچنین کامل بودن NP را برای نسخه های پیچیده تر، که به طور شهودی سخت تر به نظر می رسند و بنابراین شاید سخت تر اثبات شوند.

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

محقق جوان دیگری که از آلندر الهام گرفته شده است شویچی هیراهارا، اکنون استاد موسسه ملی انفورماتیک توکیو است. هیراهارا در حالی که در سال 2018 دانشجوی کارشناسی ارشد بود، میزان واقعی رابطه بین فراپیچیدگی و پیچیدگی متوسط ​​موردی را که کارموسینو و همکارانش کشف کرده بودند، فاش کرد. آن چهار محقق ارتباطی بین پیچیدگی متوسط ​​یک مسئله - MCSP - و پیچیدگی بدترین حالت دیگری - یادگیری بولی پیدا کرده بودند. هیراهارا تکنیک های خود را بیشتر توسعه داد استخراج کاهش بدترین حالت تا متوسط ​​مورد برای MCSP. نتیجه او حاکی از آن است که یک الگوریتم فرضی MCSP میانگین موردی مانند الگوریتمی که کارموسینو و همکارانش در نظر گرفته بودند، در واقع به اندازه کافی قدرتمند است تا بتواند نسخه کمی متفاوت از MCSP را بدون انجام هیچ اشتباهی حل کند.

نتیجه هیراهارا هیجان‌انگیز است، زیرا بسیاری از محققان بر خلاف سایر مشکلاتی که بدترین حالت تا متوسط ​​کاهش‌های آن شناخته شده است، گمان می‌کنند که MCSP کامل NP است. اگر آنها بتوانند نتایج هیراهارا را گسترش دهند تا همه الگوریتم‌های حالت متوسط ​​را پوشش دهند و سپس ثابت کنند که MCSP NP-کامل است، این ثابت می‌کند که ما در Heuristica زندگی نمی‌کنیم.

سانتانام گفت: «این واقعاً یک نتیجه زمین‌شکنی خواهد بود.

اثبات اینکه MCSP NP-complete است ممکن است به نظر سخت بیاید – بالاخره این سوال بیش از 50 سال است که باز بوده است. اما پس از یک دستیابی به موفقیت سال گذشته توسط هیراهارا، محققان اکنون بسیار نزدیکتر از آن چیزی هستند که چند سال پیش انتظار می رفت.

هیراهارا کامل بودن NP را برای گونه‌ای از مسئله به نام MCSP جزئی ثابت کرد که در آن ورودی‌های خاصی را در هر جدول حقیقت نادیده می‌گیرید. اثبات او مبتنی بر روش‌های توسعه‌یافته توسط ایلانگو بود تا نشان دهد که MCSP جزئی معادل یک مشکل به ظاهر نامرتبط است که شامل یک تکنیک رمزنگاری به نام اشتراک‌گذاری مخفی است. این روشی برای تقسیم یک پیام رمزگذاری شده بین بسیاری از افراد است به طوری که تنها زمانی می توان آن را رمزگشایی کرد که بخش خاصی از آنها با هم کار کنند.

برای هر کاربرد واقعی در رمزنگاری، می‌خواهید از قبل آن کسری را بدانید، اما با کمک ترفندهای رمزنگاری اضافی، می‌توانید سناریوی ناامیدکننده‌ای بسازید که در آن تشخیص اینکه چند نفر نیاز به همکاری دارند دشوار است. هیراهارا راهی برای اثبات NP-کامل بودن این مشکل رمزنگاری شده پیدا کرد و سپس نشان داد که این اثبات به معنای کامل بودن NP جزئی MCSP نیز هست.

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

ویلیامز گفت: "این کار شگفت انگیز است." همه فکر می‌کردند که این مشکلات جزئی تقریباً به همان سختی مشکل کامل هستند.»

موانعی برای اثبات کامل بودن NP برای نسخه کامل MCSP باقی مانده است. اما هیچکدام آن نوع موانعی نیستند که نشان دهند به یک جعبه ابزار کاملاً جدید نیاز است - ممکن است فقط یافتن راه درست برای ترکیب تکنیک های شناخته شده باشد. یک اثبات در نهایت وضعیت یکی از معدود مشکلاتی را که تا زمانی که نظریه پیچیدگی وجود دارد در برابر طبقه بندی مقاومت کرده است، حل می کند. لوین از طریق ایمیل نوشت: "این باعث فروتنی من می شود که نشان دهم به خاطر اینکه نتوانستم آن را ببینم احمق هستم :-)."

قطعات گمشده

MCSP حتی تنها مشکل فراپیچیدگی نیست که باعث پیشرفت بزرگی شده است. در سال 2020، رمزنگار Cornell Tech پاس رافائل و دانشجوی فوق لیسانسش یانی لیو یک ارتباط را کشف کرد بین یک مشکل فراپیچیدگی متفاوت و یک پروتکل رمزنگاری اساسی که مرز بین Heuristica و Pessiland، بدترین دنیای Impagliazzo را مشخص می‌کند (جایی که مشکلات NP-complete در حالت متوسط ​​سخت هستند، اما رمزنگاری هنوز غیرممکن است). این مسئله باعث می شود که آنها یک نامزد اصلی حمله به پسیلند و آنها را مورد مطالعه قرار دهند کارهای جدیدتر نشان می دهد که می تواند علیه هوریستیکا نیز کار کند.

پاس گفت: «تکه‌های مختلف پازل گم شده‌اند. برای من جادویی است که این میدان‌ها تا این حد به هم مرتبط هستند.»

هیراهارا هشدار می‌دهد که چالش‌هایی هنوز در انتظار محققانی است که قصد دارند جهان‌هایی را که ایمپاگلیازو 30 سال پیش ساخته بود، از بین ببرند. او گفت: «می‌خواهم بگویم که در مقطعی Heuristica و Pessiland حذف خواهند شد، اما مطمئن نیستم که چقدر به هم نزدیک هستیم.

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

او گفت: «سعی می‌کنم به خودم اجازه ندهم که بیش از حد معتقد باشم، زیرا سابقه کاملاً تثبیت‌شده‌ای وجود دارد که هیچ کار نمی‌کند». اما ما شاهد پیشرفت‌های بسیار هیجان‌انگیزی هستیم – راه‌هایی برای غلبه بر چیزهایی که مانند موانع به نظر می‌رسند.»

اگر محققان از تلاش‌های خود برای پاسخ به سؤال P در مقابل NP درسی گرفته‌اند - یا حتی فقط آن را درک کنند - این است که نظریه پیچیدگی خودش پیچیده است. اما این چالش دقیقاً همان چیزی است که تلاش را بسیار ارزشمند می کند.

کارموسینو گفت: «در واقع خیلی خوب است که خیلی سخت است. "من هرگز حوصله ندارم."

یادداشت سردبیر: اسکات آرونسون عضوی از مجله Quanta" هیئت مشاوره.